# Jin-Yi Cai

According to our database

Collaborative distances:

^{1}, Jin-Yi Cai authored at least 184 papers between 1986 and 2019.Collaborative distances:

## Awards

## ACM Fellow

ACM Fellow 2001, "For significant contributions to computational complexity theory, and for service to the international computer science research community.".

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2019

Approximability of the Six-vertex Model.

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms.

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Clifford gates in the Holant framework.

Theor. Comput. Sci., 2018

Complexity classification of the six-vertex model.

Inf. Comput., 2018

Dichotomy for Real Holant

^{c}Problems.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory.

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP.

SIAM J. Comput., 2017

Complexity of Counting CSP with Complex Weights.

J. ACM, 2017

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

2016

Holographic Algorithms.

Encyclopedia of Algorithms, 2016

Holant Problems.

Encyclopedia of Algorithms, 2016

Complexity Dichotomies for Counting Graph Homomorphisms.

Encyclopedia of Algorithms, 2016

A Complete Dichotomy Rises from the Capture of Vanishing Signatures.

SIAM J. Comput., 2016

Nonnegative Weighted #CSP: An Effective Complexity Dichotomy.

SIAM J. Comput., 2016

Holant Problems for 3-Regular Graphs with Complex Edge Functions.

Theory Comput. Syst., 2016

Erratum to: Signature Theory in Holographic Algorithms.

Algorithmica, 2016

2015

A Holant Dichotomy: Is the FKT Algorithm Universal?

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Matchgates Revisited.

Theory of Computing, 2014

The complexity of complex weighted Boolean #CSP.

J. Comput. Syst. Sci., 2014

A collapse theorem for holographic algorithms with matchgates on domain size at most 4.

Inf. Comput., 2014

Holographic Algorithms Beyond Matchgates.

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems.

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region.

Proceedings of the Approximation, 2014

2013

The Minimum Consistent Subset Cover Problem: A Minimization View of Data Mining.

IEEE Trans. Knowl. Data Eng., 2013

Partition functions on

*k*k-regular graphs with {0, 1}{0, 1}-vertex assignments and real edge functions.
Theor. Comput. Sci., 2013

Matchgates Revisited.

Electronic Colloquium on Computational Complexity (ECCC), 2013

A complete dichotomy rises from the capture of vanishing signatures: extended abstract.

Proceedings of the Symposium on Theory of Computing Conference, 2013

Dichotomy for Holant* Problems with Domain Size 3.

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Complexity Dichotomy for Counting Problems.

Proceedings of the Language and Automata Theory and Applications, 2013

On optimal differentially private mechanisms for count-range queries.

Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

2012

Spin systems on k-regular graphs with complex edge functions.

Theor. Comput. Sci., 2012

On differentially private frequent itemset mining.

PVLDB, 2012

Holographic reduction, interpolation and hardness.

Computational Complexity, 2012

From Holant to #CSP and Back: Dichotomy for Holant c Problems.

Algorithmica, 2012

Holographic Algorithms on Domain Size k > 2.

Proceedings of the Theory and Applications of Models of Computation, 2012

Complexity of counting CSP with complex weights.

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Gadgets and anti-gadgets leading to a complexity dichotomy.

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Inapproximability after Uniqueness Phase Transition in Two-Spin Systems.

Proceedings of the Combinatorial Optimization and Applications, 2012

2011

Computational Complexity of Holant Problems.

SIAM J. Comput., 2011

Foreword.

J. Comput. Syst. Sci., 2011

Honeynet games: a game theoretic approach to defending network monitors.

J. Comb. Optim., 2011

Dichotomy for Holant* Problems of Boolean Domain.

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities.

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

Non-negatively Weighted #CSP: An Effective Complexity Dichotomy.

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Progress in Complexity of Counting Problems.

Proceedings of the Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, 2011

2010

On blockwise symmetric signatures for matchgates.

Theor. Comput. Sci., 2010

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic.

Computational Complexity, 2010

A Dichotomy for

*k*-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions.
Proceedings of the Theory and Applications of Models of Computation, 7th Annual Conference, 2010

Holant Problems for Regular Graphs with Complex Edge Functions.

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

From Holant to #CSP and Back: Dichotomy for Holant

^{c}Problems.
Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Graph Homomorphisms with Complex Values: A Dichotomy Theorem.

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP.

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights.

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

On Tractable Exponential Sums.

Proceedings of the Frontiers in Algorithmics, 4th International Workshop, 2010

2009

Preface to Special Issue: Theory and Applications of Models of Computation (TAMC).

Mathematical Structures in Computer Science, 2009

Approximation and Hardness Results for Label Cut and Related Problems.

Proceedings of the Theory and Applications of Models of Computation, 6th Annual Conference, 2009

A Computational Proof of Complexity of Some Restricted Counting Problems.

Proceedings of the Theory and Applications of Models of Computation, 6th Annual Conference, 2009

Holant problems and counting CSP.

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

An Attacker-Defender Game for Honeynets.

Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

2008

Holographic algorithms: guest column.

SIGACT News, 2008

Basis Collapse in Holographic Algorithms.

Computational Complexity, 2008

A quadratic lower bound for the permanent and determinant problem over any characteristic != 2.

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Holographic algorithms with unsymmetric signatures.

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Signature Theory in Holographic Algorithms.

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness.

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

J. Comput. Syst. Sci., 2007

Holographic algorithms: from art to science.

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

On Symmetric Signatures in Holographic Algorithms.

Proceedings of the STACS 2007, 2007

The minimum consistent subset cover problem and its applications in data mining.

Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007

Holographic Algorithms: The Power of Dimensionality Resolved.

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

On Block-Wise Symmetric Signatures for Matchgates.

Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

A Novel Information Transmission Problem and Its Optimal Solution.

Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

Bases Collapse in Holographic Algorithms.

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

On the Theory of Matchgate Computations.

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

On zero error algorithms having oracle access to one query.

J. Comb. Optim., 2006

On the Theory of Matchgate Computations

Electronic Colloquium on Computational Complexity (ECCC), 2006

Valiant's Holant Theorem and Matchgate Tensors.

Proceedings of the Theory and Applications of Models of Computation, 2006

Some Results on Matchgates and Holographic Algorithms.

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

Progress in Computational Complexity Theory.

J. Comput. Sci. Technol., 2005

Valiant's Holant Theorem and Matchgate Tensors

Electronic Colloquium on Computational Complexity (ECCC), 2005

Simulating Undirected

*st*-Connectivity Algorithms on Uniform JAGs and NNJAGs.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

A Note on Zero Error Algorithms Having Oracle Access to One NP Query.

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004

On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy.

SIAM J. Comput., 2004

Relativized collapsing between BPP and PH under stringent oracle access.

Inf. Process. Lett., 2004

A note on quadratic residuosity and UP.

Inf. Process. Lett., 2004

Time-Space Tradeoff in Derandomizing Probabilistic Logspace.

Proceedings of the STACS 2004, 2004

Random Access to Advice Strings and Collapsing Results.

Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Mass Spectrum Labeling: Theory and Practice.

Proceedings of the 4th IEEE International Conference on Data Mining (ICDM 2004), 2004

2003

Essentially Every Unimodular Matrix Defines an Expander.

Theory Comput. Syst., 2003

A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor.

Discrete Applied Mathematics, 2003

Competing Provers Yield Improved Karp-Lipton Collapse Results.

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Estimation of Congestion Price Using Probabilistic Packet Marking.

Proceedings of the Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30, 2003

X-Diff: An Effective Change Detection Algorithm for XML Documents.

Proceedings of the 19th International Conference on Data Engineering, 2003

Stringent Relativization.

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results.

Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

2002

On the Minimum Volume of a Perturbed Unit Cube.

Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

On Higher Arthur-Merlin Classes.

Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001

Electronic Colloquium on Computational Complexity (ECCC), 2001

Essentially every unimodular matrix defines an expander

Electronic Colloquium on Computational Complexity (ECCC), 2001

On the Complexity of Join Predicates.

Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

On the Average-Case Hardness of CVP.

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

On Testing for Zero Polynomials by a Set of Points with Bounded Precision.

Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

2000

The Complexity of the A B C Problem.

SIAM J. Comput., 2000

A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.

Inf. Process. Lett., 2000

Circuit minimization problem.

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Essentially Every Unimodular Matrix Defines and Expander.

Proceedings of the Algorithms and Computation, 11th International Conference, 2000

The Complexity of Some Lattice Problems.

Proceedings of the Algorithmic Number Theory, 4th International Symposium, 2000

1999

Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis.

J. Comput. Syst. Sci., 1999

Approximating the SVP to within a Factor (1+1/dim

^{xi}) Is NP-Hard under Randomized Reductions.
J. Comput. Syst. Sci., 1999

A Classification of the Probabilistic Polynomial Time Hierarchy Under Fault Tolerant Access to Oracle Classes.

Inf. Process. Lett., 1999

Circuit Minimization Problem

Electronic Colloquium on Computational Complexity (ECCC), 1999

Some Recent Progress on the Complexity of Lattice Problems

Electronic Colloquium on Computational Complexity (ECCC), 1999

Foreword.

Algorithmica, 1999

Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time.

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

On the Hardness of Permanent.

Proceedings of the STACS 99, 1999

On Routing in Circulant Graphs.

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

A New Transference Theorem in the Geometry of Numbers.

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

Applications of a New Transference Theorem to Ajtai's Connection Factor.

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

Some Recent Progress on the Complexity of Lattice Problems.

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

A Relation of Primal-Dual Lattices and the Complexity of Shortest Lattice Vector Problem.

Theor. Comput. Sci., 1998

Frobenius's Degree Formula and Toda's Polynomials.

Theory Comput. Syst., 1998

Efficient Algorithms for a Scheduling Problem and its Applications to Illicit Drug Market Crackdowns.

J. Comb. Optim., 1998

On A Scheduling Problem of Time Deteriorating Jobs.

J. Complexity, 1998

A new transference theorem and applications to Ajtai's connection factor

Electronic Colloquium on Computational Complexity (ECCC), 1998

A Lattice-Based Public-Key Cryptosystem.

Proceedings of the Selected Areas in Cryptography '98, 1998

Robust Reductions.

Proceedings of the Computing and Combinatorics, 4th Annual International Conference, 1998

Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions.

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

Approximating the SVP to within a factor (1 + 1/dim

^{epsilon}) is NP-hard under randomized reductions
Electronic Colloquium on Computational Complexity (ECCC), 1997

Constant Depth Circuits and the Lutz Hypothesis.

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

An Improved Worst-Case to Average-Case Connection for Lattice Problems.

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Resolution of Hartmanis' Conjecture for NL-Hard Sparse Sets.

Proceedings of the Computing and Combinatorics, Third Annual International Conference, 1997

On the 100% Rule of Sensivity Analzsis in Linear Programming.

Proceedings of the Computing and Combinatorics, Third Annual International Conference, 1997

1996

The Bounded Membership Problem of the Monoid SL_2(N).

Mathematical Systems Theory, 1996

On the Correlation of Symmetric Functions.

Mathematical Systems Theory, 1996

Fine Separation of Average Time Complexity Classes.

Proceedings of the STACS 96, 1996

On the Existence of Hard Sparse Sets under Weak Reductions.

Proceedings of the STACS 96, 1996

Multiplicative Equations over Commuting Matrices.

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

1995

On the Impossibility of Amplifying the Independence of Random Variables.

Random Struct. Algorithms, 1995

Average Time Complexity Classes

Electronic Colloquium on Computational Complexity (ECCC), 1995

Pseudorandom Generators, Measure Theory, and Natural Proofs

Electronic Colloquium on Computational Complexity (ECCC), 1995

Communication Complexity of Key Agreement on Small Ranges.

STACS, 1995

Pseudorandom Generators, Measure Theory, and Natural Proofs.

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

The Resolution of a Hartmanis Conjecture.

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Subquadratic Simulations of Balanced Formulae by Branching Programs.

SIAM J. Comput., 1994

On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line.

J. Comput. Syst. Sci., 1994

Computing Jordan Normal Forms Exactly for Commuting Matrices in Polynomial Time.

Int. J. Found. Comput. Sci., 1994

Reliable Benchmarks Using Numerical Instability.

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic Geometry.

Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Efficient Average-Case Algorithms for the Modular Group

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

Taking Random Walks to Grow Trees in Hypercubes.

J. ACM, 1993

Towards Uncheatable benchmarks.

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

On Games of Incomplete Information.

Theor. Comput. Sci., 1992

An optimal lower bound on the number of variables for graph identifications.

Combinatorica, 1992

Parallel Computation Over Hyperbolic Groups

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Promise Problems and Access to Unambiguous Computation.

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Promise Problems and Guarded Access to Unambiguous Computation.

Proceedings of the Complexity Theory: Current Research, 1992

1991

A Note on Enumarative Counting.

Inf. Process. Lett., 1991

PSPACE Survives Constant-Width Bottlenecks.

Int. J. Found. Comput. Sci., 1991

Computations Over Infinite Groups.

Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

PSPACE Is Provable By Two Provers In One Round.

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990

A Note on the Determinant and Permanent Problem

Inf. Comput., January, 1990

Lower Bounds for Constant-Depth Circuits in the Presence of Help Bits.

Inf. Process. Lett., 1990

Playing Games of Incomplete Information.

Proceedings of the STACS 90, 1990

On Bounded Round Multi-Prover Interactive Proof Systems.

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

Enumerative Counting Is Hard

Inf. Comput., July, 1989

The Boolean Hierarchy II: Applications.

SIAM J. Comput., 1989

With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy.

J. Comput. Syst. Sci., 1989

On the Power of Parity Polynomial Time.

Proceedings of the STACS 89, 1989

Subquadratic Simulations of Circuits by Branching Programs

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

An Optimal Lower Bound on the Number of Variables for Graph Identification

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Lower Bounds for Constant Depth Circuits in the Presence of Help Bits

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

The Complexity Of The Real Line Is A Fractal.

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

The Boolean Hierarchy I: Structural Properties.

SIAM J. Comput., 1988

Take a Walk, Grow a Tree (Preliminary Version)

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Enumerative counting is hard.

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

Graph Minimal Uncolorability is D^P-Complete.

SIAM J. Comput., 1987

Probability One Separation of the Boolean Hierarchy.

Proceedings of the STACS 87, 1987

On the Complexity of Graph Critical Uncolorability.

Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

PSPACE survives three-bit bottlenecks.

Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986

With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

The Boolean Hierarchy: Hardware over NP.

Proceedings of the Structure in Complexity Theory, 1986

With Probability One, A Random Oracle Separates PSPACE from the Polynomial- Time Hierarchy.

Proceedings of the Structure in Complexity Theory, 1986