JinYi Cai
According to our database^{1},
JinYi Cai
authored at least 186 papers
between 1986 and 2020.
Collaborative distances:
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 OtherLinks
Homepages:

at zbmath.org
On csauthors.net:
Bibliography
2020
A dichotomy for bounded degree graph homomorphisms with nonnegative weights.
CoRR, 2020
On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020
2019
Gadgets and AntiGadgets Leading to a Complexity Dichotomy.
TOCT, 2019
On a Theorem of Lovász that hom(·, H) Determines the Isomorhphism Type of H.
CoRR, 2019
Counting perfect matchings and the eightvertex model.
CoRR, 2019
Complexity of Counting Weighted Eulerian Orientations with ARS.
CoRR, 2019
A decidable dichotomy theorem on directed graph homomorphisms with nonnegative weights.
Computational Complexity, 2019
Approximability of the Sixvertex Model.
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms.
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
2018
Clifford gates in the Holant framework.
Theor. Comput. Sci., 2018
Holographic algorithms beyond matchgates.
Inf. Comput., 2018
Complexity classification of the sixvertex model.
Inf. Comput., 2018
Approximability of the Eightvertex Model.
CoRR, 2018
Dichotomy for Real Holant^{c} Problems.
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
A Complexity Trichotomy for kRegular 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
Dichotomy for Real Holant^{c} Problems.
CoRR, 2017
A Complexity Trichotomy for the SixVertex Model.
CoRR, 2017
Complexity Classification of the EightVertex Model.
CoRR, 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 3Regular Graphs with Complex Edge Functions.
Theory Comput. Syst., 2016
#BIShardness for 2spin systems on bipartite bounded degree graphs in the tree nonuniqueness region.
J. Comput. Syst. Sci., 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
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
2013
The Minimum Consistent Subset Cover Problem: A Minimization View of Data Mining.
IEEE Trans. Knowl. Data Eng., 2013
Partition functions on kkregular graphs with {0, 1}{0, 1}vertex assignments and real edge functions.
Theor. Comput. Sci., 2013
Graph Homomorphisms with Complex Values: A Dichotomy Theorem.
SIAM J. Comput., 2013
Approximating the Partition Function of TwoSpin Systems on Bipartite Graphs.
CoRR, 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 TwentyFourth Annual ACMSIAM 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 countrange queries.
Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013
2012
Spin systems on kregular graphs with complex edge functions.
Theor. Comput. Sci., 2012
On differentially private frequent itemset mining.
PVLDB, 2012
Dichotomy for Holant* Problems with a Function on Domain Size 3
CoRR, 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
Inapproximability after Uniqueness Phase Transition in TwoSpin Systems.
Proceedings of the Combinatorial Optimization and Applications, 2012
2011
A computational proof of complexity of some restricted counting problems.
Theor. Comput. Sci., 2011
Computational Complexity of Holant Problems.
SIAM J. Comput., 2011
Foreword.
J. Comput. Syst. Sci., 2011
Holographic algorithms: From art to science.
J. Comput. Syst. Sci., 2011
Approximation and hardness results for label cut and related problems.
J. Comb. Optim., 2011
Honeynet games: a game theoretic approach to defending network monitors.
J. Comb. Optim., 2011
Signature Theory in Holographic Algorithms.
Algorithmica, 2011
Dichotomy for Holant* Problems of Boolean Domain.
Proceedings of the TwentySecond Annual ACMSIAM 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
Nonnegatively 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
Nonnegative Weighted #CSPs: An Effective Complexity Dichotomy
CoRR, 2010
Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic.
Computational Complexity, 2010
A Dichotomy for kRegular 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
Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP.
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
Holographic algorithms: The power of dimensionality resolved.
Theor. Comput. Sci., 2009
On the Theory of Matchgate Computations.
Theory Comput. Syst., 2009
Preface to Special Issue: Theory and Applications of Models of Computation (TAMC).
Mathematical Structures in Computer Science, 2009
Holant problems and counting CSP.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009
An AttackerDefender Game for Honeynets.
Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009
2008
Holographic algorithms: guest column.
SIGACT News, 2008
A Family of Counter Examples to an Approach to Graph Isomorphism
CoRR, 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 ACMSIAM Symposium on Discrete Algorithms, 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
Valiant's Holant Theorem and matchgate tensors.
Theor. Comput. Sci., 2007
S_{2}^{p} is subset of ZPP^{NP}.
J. Comput. Syst. Sci., 2007
On Blockwise Symmetric Signatures for Matchgates.
Electronic Colloquium on Computational Complexity (ECCC), 2007
Bases Collapse in Holographic Algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 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
A Novel Information Transmission Problem and Its Optimal Solution.
Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007
2006
TimeSpace Tradeoff in Derandomizing Probabilistic Logspace.
Theory Comput. Syst., 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
On Symmetric Signatures in Holographic Algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 2006
Some Results on Matchgates and Holographic Algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 2006
Random Access to Advice Strings and Collapsing Results.
Algorithmica, 2006
2005
Progress in Computational Complexity Theory.
J. Comput. Sci. Technol., 2005
Competing provers yield improved KarpLipton collapse results.
Inf. Comput., 2005
Simulating Undirected stConnectivity 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 PolynomialTime 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
On Higher ArthurMerlin Classes.
Int. J. Found. Comput. Sci., 2004
Mass Spectrum Labeling: Theory and Practice.
Proceedings of the 4th IEEE International Conference on Data Mining (ICDM 2004), 2004
2003
On testing for zero polynomials by a set of points with bounded precision.
Theor. Comput. Sci., 2003
A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor.
Discret. Appl. Math., 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
XDiff: 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 PolynomialTime 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
2001
S_2^{p} \subseteq ZPP^{NP}
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 SIGACTSIGMODSIGART Symposium on Principles of Database Systems, 2001
S^{p}_{2} subseteq ZPP^{NP}.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
On the AverageCase Hardness of CVP.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
2000
Resolution of Hartmanis' conjecture for NLhard sparse sets.
Theor. Comput. Sci., 2000
The Complexity of the A B C Problem.
SIAM J. Comput., 2000
A note on the nonNPhardness of approximate lattice problems under general Cook reductions.
Inf. Process. Lett., 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
Fine Separation of AverageTime Complexity Classes.
SIAM J. Comput., 1999
Robust Reductions.
Theory Comput. Syst., 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 NPHard 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
A LatticeBased PublicKey Cryptosystem.
Inf. Comput., 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 QuasiPolynomial Time.
Proceedings of the ThirtyFirst 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
1998
A Relation of PrimalDual 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. Complex., 1998
A new transference theorem and applications to Ajtai's connection factor
Electronic Colloquium on Computational Complexity (ECCC), 1998
Approximating the SVP to within a Factor is NPHard 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 NPhard 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 WorstCase to AverageCase Connection for Lattice Problems.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 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
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 ACMSIAM 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.
Proceedings of the STACS 95, 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
PSPACE Is Provable by Two Provers in One Round.
J. Comput. Syst. Sci., 1994
Computing Jordan Normal Forms Exactly for Commuting Matrices in Polynomial Time.
Int. J. Found. Comput. Sci., 1994
Efficient AverageCase Algorithms for the Modular Group
Electronic Colloquium on Computational Complexity (ECCC), 1994
Reliable Benchmarks Using Numerical Instability.
Proceedings of the Fifth Annual ACMSIAM Symposium on Discrete Algorithms. 2325 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 2generated Commutative Semigroups of Rational Matrices
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, San Diego, 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 ConstantWidth Bottlenecks.
Int. J. Found. Comput. Sci., 1991
Computations Over Infinite Groups.
Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991
1990
A Note on the Determinant and Permanent Problem
Inf. Comput., January, 1990
On the Power of Parity Polynomial Time.
Mathematical Systems Theory, 1990
Lower Bounds for ConstantDepth 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 MultiProver 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 PolynomialTime Hierarchy.
J. Comput. Syst. Sci., 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
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
1987
Graph Minimal Uncolorability is D^PComplete.
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 threebit bottlenecks.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987
1986
The Boolean Hierarchy: Hardware over NP.
Proceedings of the Structure in Complexity Theory, 1986