research
∙
07/29/2023
Restricted Holant Dichotomy on Domains 3 and 4
Holant^*(f) denotes a class of counting problems specified by a constrai...
share
research
∙
06/15/2023
Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise
We consider Shor's quantum factoring algorithm in the setting of noisy q...
research
∙
03/29/2023
Planar 3-way Edge Perfect Matching Leads to A Holant Dichotomy
We prove a complexity dichotomy theorem for a class of Holant problems o...
research
∙
03/05/2023
Properties of Position Matrices and Their Elections
We study the properties of elections that have a given position matrix (...
research
∙
02/16/2023
The complexity of counting planar graph homomorphisms of domain size 3
We prove a complexity dichotomy theorem for counting planar graph homomo...
research
∙
12/06/2022
Planar #CSP Equality Corresponds to Quantum Isomorphism – A Holant Viewpoint
Recently, Mančinska and Roberson proved that two graphs G and G' are qua...
research
∙
08/21/2022
Counting Cycles on Planar Graphs in Subexponential Time
We study the problem of counting all cycles or self-avoiding walks (SAWs...
research
∙
10/04/2021
Bipartite 3-Regular Counting Problems with Mixed Signs
We prove a complexity dichotomy for a class of counting problems express...
research
∙
11/18/2020
Dichotomy Result on 3-Regular Bipartite Non-negative Functions
We prove a complexity dichotomy theorem for a class of Holant problems o...
research
∙
10/12/2020
FPRAS via MCMC where it mixes torpidly (and very little effort)
Is Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for a p...
research
∙
10/10/2020
The Complexity of Counting Edge Colorings for Simple Graphs
We prove #P-completeness results for counting edge colorings on simple g...
research
∙
05/16/2020
A Dichotomy for Real Boolean Holant Problems
We prove a complexity dichotomy for Holant problems on the boolean domai...
research
∙
04/14/2020
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs
The complexity of graph homomorphisms has been a subject of intense stud...
research
∙
04/12/2020
From Holant to Quantum Entanglement and Back
Holant problems are intimately connected with quantum theory as tensor n...
research
∙
02/05/2020
A dichotomy for bounded degree graph homomorphisms with nonnegative weights
We consider the complexity of counting weighted graph homomorphisms defi...
research
∙
09/09/2019
On a Theorem of Lovász that (·, H) Determines the Isomorhphism Type of H
Graph homomorphism has been an important research topic since its introd...
research
∙
09/07/2019
Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms
We develop a theory of graph algebras over general fields. This is model...
research
∙
04/23/2019
Counting perfect matchings and the eight-vertex model
We study the approximation complexity of the partition function of the e...
research
∙
04/04/2019
Complexity of Counting Weighted Eulerian Orientations with ARS
Unique prime factorization of integers is taught in every high school. W...
research
∙
11/07/2018
Approximability of the Eight-vertex Model
We initiate a study of the classification of approximation complexity of...
research
∙
12/16/2017