| Publication | Date of Publication | Type |
|---|
Restricted Holant dichotomy on domain sizes 3 and 4
Theoretical Computer Science | 2024-12-12 | Paper |
| Planar \#CSP equality corresponds to quantum isomorphism -- A Holant viewpoint | 2024-11-14 | Paper |
| Restricted Holant dichotomy on domains 3 and 4 | 2024-09-16 | Paper |
| Bounded degree nonnegative counting CSP | 2024-08-06 | Paper |
| The complexity of counting planar graph homomorphisms of domain size 3 | 2024-05-08 | Paper |
Counting cycles on planar graphs in subexponential time
Algorithmica | 2024-01-25 | Paper |
| scientific article; zbMATH DE number 7788430 (Why is no real title available?) | 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788431 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Counting cycles on planar graphs in subexponential time
Lecture Notes in Computer Science | 2023-08-10 | Paper |
Holographic algorithms on domains of general size
Theory of Computing Systems | 2023-07-26 | Paper |
Complexity classification of the eight-vertex model
Information and Computation | 2023-07-17 | Paper |
A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
Computational Complexity | 2023-07-10 | Paper |
Where Tutte and Holant meet: a view from counting complexity
Handbook of the Tutte Polynomial and Related Topics | 2023-04-28 | Paper |
Perfect matchings, rank of connection tensors and graph homomorphisms
Combinatorics, Probability and Computing | 2023-03-31 | Paper |
Dichotomy result on 3-regular bipartite non-negative functions
Theoretical Computer Science | 2023-02-24 | Paper |
scientific article; zbMATH DE number 7650365 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
A dichotomy for bounded degree graph homomorphisms with nonnegative weights
Journal of Computer and System Sciences | 2023-01-09 | Paper |
| Planar #CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint | 2022-12-06 | Paper |
Promise problems and access to unambiguous computation
Mathematical Foundations of Computer Science 1992 | 2022-08-18 | Paper |
On the power of parity polynomial time
STACS 89 | 2022-08-16 | Paper |
Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
SIAM Journal on Computing | 2022-05-03 | Paper |
On a theorem of Lovász that \((\cdot, H)\) determines the isomorphism type of \(H\)
ACM Transactions on Computation Theory | 2022-03-22 | Paper |
Dichotomy result on 3-regular bipartite non-negative functions
Computer Science – Theory and Applications | 2022-03-21 | Paper |
FKT is not universal -- a planar holant dichotomy for symmetric constraints
Theory of Computing Systems | 2022-02-14 | Paper |
The complexity of counting edge colorings for simple graphs
Theoretical Computer Science | 2021-10-06 | Paper |
| A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory | 2021-06-15 | Paper |
Dichotomy for Holant\(^\ast\) problems on the Boolean domain
Theory of Computing Systems | 2021-06-11 | Paper |
Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
Information and Computation | 2020-12-15 | Paper |
| Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs | 2020-04-14 | Paper |
Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
ACM Transactions on Computation Theory | 2019-12-16 | Paper |
Approximability of the Six-vertex Model
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Perfect matchings, rank of connection tensors and graph homomorphisms
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
On a Theorem of Lov\'asz that $\hom(\cdot, H)$ Determines the Isomorphism Type of $H$
(available as arXiv preprint) | 2019-09-09 | Paper |
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
Computational Complexity | 2019-08-30 | Paper |
Dichotomy for Holant* problems with a function on domain size 3
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Clifford gates in the Holant framework
Theoretical Computer Science | 2018-09-24 | Paper |
Complexity of counting CSP with complex weights
Journal of the ACM | 2018-05-17 | Paper |
Complexity classification of the six-vertex model
Information and Computation | 2018-03-21 | Paper |
Holographic algorithms beyond matchgates
Information and Computation | 2018-03-21 | Paper |
| Dichotomy for real Holant\(^{\mathrm c}\) problems | 2018-03-15 | Paper |
Dichotomy for real Holant\(^{\mathrm c}\) problems
(available as arXiv preprint) | 2018-03-15 | Paper |
| Complexity Dichotomies for Counting Problems | 2018-01-02 | Paper |
Fine separation of average time complexity classes
STACS 96 | 2017-11-16 | Paper |
| Dichotomy for Holant* problems of Boolean domain | 2017-09-29 | Paper |
Holographic algorithm with matchgates is universal for planar \#CSP over Boolean domain
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Holographic algorithms with matchgates capture precisely tractable planar \#CSP
SIAM Journal on Computing | 2017-05-30 | Paper |
| \#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region | 2017-03-22 | Paper |
Nonnegative weighted \#CSP: an effective complexity dichotomy
SIAM Journal on Computing | 2016-12-21 | Paper |
Gadgets and anti-gadgets leading to a complexity dichotomy
Proceedings of the 3rd Innovations in Theoretical Computer Science Conference | 2016-10-07 | Paper |
Hardness and hierarchy theorems for probabilistic quasi-polynomial time
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Holant problems for 3-regular graphs with complex edge functions
Theory of Computing Systems | 2016-09-21 | Paper |
The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
Research in the Mathematical Sciences | 2016-09-09 | Paper |
A complete dichotomy rises from the capture of vanishing signatures
SIAM Journal on Computing | 2016-09-02 | Paper |
A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes
Information Processing Letters | 2016-06-16 | Paper |
Erratum to: ``Signature theory in holographic algorithms
Algorithmica | 2016-05-31 | Paper |
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
Journal of Computer and System Sciences | 2016-04-18 | Paper |
Holant problems and counting CSP
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
A collapse theorem for holographic algorithms with matchgates on domain size at most 4
Information and Computation | 2014-11-28 | Paper |
Matchgates revisited
Theory of Computing | 2014-10-06 | Paper |
Circuit minimization problem
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
A complete dichotomy rises from the capture of vanishing signatures (extended abstract)
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Holographic algorithms beyond matchgates
Lecture Notes in Computer Science | 2014-07-01 | Paper |
Complexity of counting CSP with complex weights
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
The complexity of complex weighted Boolean \#CSP
Journal of Computer and System Sciences | 2014-01-28 | Paper |
Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
Theoretical Computer Science | 2014-01-10 | Paper |
Graph homomorphisms with complex values: a dichotomy theorem
SIAM Journal on Computing | 2013-09-25 | Paper |
Complexity dichotomy for counting problems
Language and Automata Theory and Applications | 2013-03-18 | Paper |
From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
Algorithmica | 2013-01-28 | Paper |
Holographic algorithms by Fibonacci gates
Linear Algebra and its Applications | 2013-01-16 | Paper |
Holographic reduction, interpolation and hardness
Computational Complexity | 2012-12-27 | Paper |
Spin systems on \(k\)-regular graphs with complex edge functions
Theoretical Computer Science | 2012-11-27 | Paper |
Inapproximability after uniqueness phase transition in two-spin systems
Combinatorial Optimization and Applications | 2012-11-02 | Paper |
Holographic algorithms on domain size \(k > 2\)
Lecture Notes in Computer Science | 2012-07-16 | Paper |
| Holant problems for regular graphs with complex edge functions | 2012-01-23 | Paper |
Honeynet games: A game theoretic approach to defending network monitors
Journal of Combinatorial Optimization | 2011-12-15 | Paper |
Signature theory in holographic algorithms
Algorithmica | 2011-12-14 | Paper |
Computational complexity of Holant problems
SIAM Journal on Computing | 2011-11-07 | Paper |
Spin systems on graphs with complex edge functions and specified degree regularities
Lecture Notes in Computer Science | 2011-08-17 | Paper |
Progress in complexity of counting problems
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management | 2011-06-03 | Paper |
A computational proof of complexity of some restricted counting problems
Theoretical Computer Science | 2011-05-18 | Paper |
On proving circuit lower bounds against the polynomial-time hierarchy: positive and negative results
Lecture Notes in Computer Science | 2011-03-18 | Paper |
Approximation and hardness results for label cut and related problems
Journal of Combinatorial Optimization | 2011-03-17 | Paper |
Quadratic lower bound for permanent vs. determinant in any characteristic
Computational Complexity | 2011-02-07 | Paper |
Holographic algorithms: from art to science
Journal of Computer and System Sciences | 2011-01-18 | Paper |
From Holant to \#CSP and back: dichotomy for Holant\(^{c }\) problems
Algorithms and Computation | 2010-12-09 | Paper |
On tractable exponential sums
Frontiers in Algorithmics | 2010-09-07 | Paper |
Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
Automata, Languages and Programming | 2010-09-07 | Paper |
| scientific article; zbMATH DE number 5764803 (Why is no real title available?) | 2010-08-06 | Paper |
A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions
Lecture Notes in Computer Science | 2010-06-17 | Paper |
On symmetric signatures in holographic algorithms
Theory of Computing Systems | 2010-05-05 | Paper |
A novel information transmission problem and its optimal solution
Communications in Information and Systems | 2010-04-13 | Paper |
On blockwise symmetric signatures for matchgates
Theoretical Computer Science | 2010-02-09 | Paper |
On the theory of matchgate computations
Theory of Computing Systems | 2009-09-18 | Paper |
A note on quadratic residuosity and UP
Information Processing Letters | 2009-08-27 | Paper |
FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
Lecture Notes in Computer Science | 2009-08-06 | Paper |
An Attacker-Defender Game for Honeynets
Lecture Notes in Computer Science | 2009-07-23 | Paper |
Relativized collapsing between BPP and PH under stringent oracle access
Information Processing Letters | 2009-07-21 | Paper |
Approximation and Hardness Results for Label Cut and Related Problems
Lecture Notes in Computer Science | 2009-06-03 | Paper |
A Computational Proof of Complexity of Some Restricted Counting Problems
Lecture Notes in Computer Science | 2009-06-03 | Paper |
Holographic algorithms: the power of dimensionality resolved
Theoretical Computer Science | 2009-04-29 | Paper |
Some Results on Matchgates and Holographic Algorithms
Automata, Languages and Programming | 2009-03-12 | Paper |
| Holographic algorithms | 2009-02-09 | Paper |
Signature Theory in Holographic Algorithms
Algorithms and Computation | 2009-01-29 | Paper |
| Holographic algorithms: from art to science | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5485561 (Why is no real title available?) | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5368607 (Why is no real title available?) | 2008-11-19 | Paper |
Basis collapse in holographic algorithms
Computational Complexity | 2008-08-20 | Paper |
A Novel Information Transmission Problem and Its Optimal Solution
Fundamentals of Computation Theory | 2008-02-26 | Paper |
On Block-Wise Symmetric Signatures for Matchgates
Fundamentals of Computation Theory | 2008-02-26 | Paper |
Holographic Algorithms: The Power of Dimensionality Resolved
Automata, Languages and Programming | 2007-11-28 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
Valiant's holant theorem and matchgate tensors
Theoretical Computer Science | 2007-09-28 | Paper |
On Symmetric Signatures in Holographic Algorithms
STACS 2007 | 2007-09-03 | Paper |
Theory and Applications of Models of Computation
Lecture Notes in Computer Science | 2007-04-30 | Paper |
\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
Journal of Computer and System Sciences | 2007-01-22 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2006-11-14 | Paper |
Time-space tradeoff in derandomizing probabilistic logspace
Theory of Computing Systems | 2006-10-25 | Paper |
Random access to advice strings and collapsing results
Algorithmica | 2006-10-16 | Paper |
On zero error algorithms having oracle access to one query
Journal of Combinatorial Optimization | 2006-08-14 | Paper |
Computing and Combinatorics
Lecture Notes in Computer Science | 2006-01-11 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2005-12-22 | Paper |
ON HIGHER ARTHUR-MERLIN CLASSES
International Journal of Foundations of Computer Science | 2005-10-19 | Paper |
Competing provers yield improved Karp-Lipton collapse results
Information and Computation | 2005-05-04 | Paper |
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy
SIAM Journal on Computing | 2005-02-21 | Paper |
| scientific article; zbMATH DE number 2089956 (Why is no real title available?) | 2004-08-12 | Paper |
| scientific article; zbMATH DE number 2080231 (Why is no real title available?) | 2004-08-04 | Paper |
| scientific article; zbMATH DE number 1979488 (Why is no real title available?) | 2003-09-14 | Paper |
Essentially every unimodular matrix defines an expander
Theory of Computing Systems | 2003-08-27 | Paper |
On testing for zero polynomials by a set of points with bounded precision.
Theoretical Computer Science | 2003-08-17 | Paper |
| scientific article; zbMATH DE number 1962842 (Why is no real title available?) | 2003-08-11 | Paper |
A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor
Discrete Applied Mathematics | 2003-03-09 | Paper |
A lattice-based public-key cryptosystem
Information and Computation | 2003-01-14 | Paper |
A New Transference Theorem in the Geometry of Numbers
Lecture Notes in Computer Science | 2002-10-10 | Paper |
| scientific article; zbMATH DE number 1796989 (Why is no real title available?) | 2002-09-05 | Paper |
| scientific article; zbMATH DE number 1643917 (Why is no real title available?) | 2002-07-09 | Paper |
| scientific article; zbMATH DE number 1555932 (Why is no real title available?) | 2001-01-24 | Paper |
A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
Information Processing Letters | 2000-12-12 | Paper |
The Complexity of theA B CProblem
SIAM Journal on Computing | 2000-10-18 | Paper |
Robust reductions
Theory of Computing Systems | 2000-03-07 | Paper |
Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
Journal of Computer and System Sciences | 2000-01-17 | Paper |
Fine Separation of Average-Time Complexity Classes
SIAM Journal on Computing | 1999-10-28 | Paper |
| scientific article; zbMATH DE number 1304121 (Why is no real title available?) | 1999-10-05 | Paper |
| scientific article; zbMATH DE number 1346527 (Why is no real title available?) | 1999-10-03 | Paper |
| scientific article; zbMATH DE number 1335879 (Why is no real title available?) | 1999-09-13 | Paper |
| scientific article; zbMATH DE number 1222831 (Why is no real title available?) | 1999-05-18 | Paper |
On a scheduling problem of time deteriorating jobs
Journal of Complexity | 1999-02-16 | Paper |
A relation of primal--dual lattices and the complexity of shortest lattice vector problem
Theoretical Computer Science | 1999-01-12 | Paper |
Efficient algorithms for a scheduling problem and its applications to illicit drug market crackdowns
Journal of Combinatorial Optimization | 1998-05-25 | Paper |
Frobenius's degree formula and Toda's polynomials
Theory of Computing Systems | 1998-05-25 | Paper |
| scientific article; zbMATH DE number 1088284 (Why is no real title available?) | 1997-11-17 | Paper |
| scientific article; zbMATH DE number 1003232 (Why is no real title available?) | 1997-10-16 | Paper |
| scientific article; zbMATH DE number 1072529 (Why is no real title available?) | 1997-10-08 | Paper |
On the correlation of symmetric functions
Mathematical Systems Theory | 1996-12-01 | Paper |
On the correlation of symmetric functions
Mathematical Systems Theory | 1996-09-09 | Paper |
On the impossibility of amplifying the independence of random variables
Random Structures & Algorithms | 1996-08-27 | Paper |
| scientific article; zbMATH DE number 871949 (Why is no real title available?) | 1996-06-18 | Paper |
COMPUTING JORDAN NORMAL FORMS EXACTLY FOR COMMUTING MATRICES IN POLYNOMIAL TIME
International Journal of Foundations of Computer Science | 1995-10-29 | Paper |
On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
Journal of Computer and System Sciences | 1995-01-15 | Paper |
| scientific article; zbMATH DE number 512802 (Why is no real title available?) | 1994-08-31 | Paper |
Subquadratic Simulations of Balanced Formulae by Branching Programs
SIAM Journal on Computing | 1994-08-14 | Paper |
PSPACE is provable by two provers in one round
Journal of Computer and System Sciences | 1994-04-27 | Paper |
Taking random walks to grow trees in hypercubes
Journal of the ACM | 1993-12-09 | Paper |
An optimal lower bound on the number of variables for graph identification
Combinatorica | 1993-03-10 | Paper |
On games of incomplete information
Theoretical Computer Science | 1993-01-16 | Paper |
PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
International Journal of Foundations of Computer Science | 1992-06-28 | Paper |
| scientific article; zbMATH DE number 18527 (Why is no real title available?) | 1992-06-26 | Paper |
A note on enumerative counting
Information Processing Letters | 1991-01-01 | Paper |
A note on the determinant and permanent problem
Information and Computation | 1990-01-01 | Paper |
On the power of parity polynomial time
Mathematical Systems Theory | 1990-01-01 | Paper |
Lower bounds for constant-depth circuits in the presence of help bits
Information Processing Letters | 1990-01-01 | Paper |
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
Journal of Computer and System Sciences | 1989-01-01 | Paper |
The Boolean Hierarchy II: Applications
SIAM Journal on Computing | 1989-01-01 | Paper |
Enumerative counting is hard
Information and Computation | 1989-01-01 | Paper |
The Boolean Hierarchy I: Structural Properties
SIAM Journal on Computing | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4024813 (Why is no real title available?) | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4033067 (Why is no real title available?) | 1987-01-01 | Paper |
Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
SIAM Journal on Computing | 1987-01-01 | Paper |
The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
SIAM Journal on Algebraic Discrete Methods | 1986-01-01 | Paper |
A Uniformly Random Solution to Algorithmic Redistricting
(available as arXiv preprint) | N/A | Paper |
