JinYi Cai
Affiliations: University of WisconsinMadison, Madison, USA
According to our database^{1},
JinYi Cai
authored at least 199 papers
between 1986 and 2022.
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
Online presence:

on zbmath.org

on cs.wisc.edu
On csauthors.net:
Bibliography
2022
Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain.
SIAM J. Comput., 2022
Theory Comput. Syst., 2022
Comb. Probab. Comput., 2022
2021
On a Theorem of Lovász that (&sdot, <i>H</i>) Determines the Isomorphism Type of <i>H</i>.
ACM Trans. Comput. Theory, 2021
Theor. Comput. Sci., 2021
An FPTAS for the square lattice sixvertex and eightvertex models at low temperatures.
Proceedings of the 2021 ACMSIAM Symposium on Discrete Algorithms, 2021
New Planar Ptime Computable SixVertex Models and a Complete Complexity Classification.
Proceedings of the 2021 ACMSIAM Symposium on Discrete Algorithms, 2021
Proceedings of the Fundamentals of Computation Theory  23rd International Symposium, 2021
Proceedings of the Computer Science  Theory and Applications, 2021
2020
Theory Comput. Syst., 2020
Inf. Comput., 2020
CoRR, 2020
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020
Proceedings of the 35th Computational Complexity Conference, 2020
2019
ACM Trans. Comput. Theory, 2019
CoRR, 2019
CoRR, 2019
A decidable dichotomy theorem on directed graph homomorphisms with nonnegative weights.
Comput. Complex., 2019
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
2018
Theor. Comput. Sci., 2018
Inf. Comput., 2018
Inf. Comput., 2018
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
SIAM J. Comput., 2017
J. ACM, 2017
CoRR, 2017
CoRR, 2017
CoRR, 2017
2016
Encyclopedia of Algorithms, 2016
Encyclopedia of Algorithms, 2016
Encyclopedia of Algorithms, 2016
SIAM J. Comput., 2016
SIAM J. Comput., 2016
Theory Comput. Syst., 2016
#BIShardness for 2spin systems on bipartite bounded degree graphs in the tree nonuniqueness region.
J. Comput. Syst. Sci., 2016
Algorithmica, 2016
2015
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015
2014
Theory Comput., 2014
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
IEEE Trans. Knowl. Data Eng., 2013
Partition functions on <i>k</i>kregular graphs with {0, 1}{0, 1}vertex assignments and real edge functions.
Theor. Comput. Sci., 2013
SIAM J. Comput., 2013
CoRR, 2013
A complete dichotomy rises from the capture of vanishing signatures: extended abstract.
Proceedings of the Symposium on Theory of Computing Conference, 2013
Proceedings of the TwentyFourth Annual ACMSIAM Symposium on Discrete Algorithms, 2013
Proceedings of the Language and Automata Theory and Applications, 2013
Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013
2012
Theor. Comput. Sci., 2012
Proc. VLDB Endow., 2012
CoRR, 2012
Comput. Complex., 2012
Algorithmica, 2012
Proceedings of the Theory and Applications of Models of Computation, 2012
Proceedings of the Combinatorial Optimization and Applications, 2012
2011
Theor. Comput. Sci., 2011
SIAM J. Comput., 2011
J. Comput. Syst. Sci., 2011
J. Comput. Syst. Sci., 2011
J. Comb. Optim., 2011
J. Comb. Optim., 2011
Algorithmica, 2011
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
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011
Proceedings of the Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, 2011
2010
Theor. Comput. Sci., 2010
CoRR, 2010
Comput. Complex., 2010
A Dichotomy for <i>k</i>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
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010
Proceedings of the Algorithms and Computation  21st International Symposium, 2010
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010
Proceedings of the Frontiers in Algorithmics, 4th International Workshop, 2010
2009
Theor. Comput. Sci., 2009
Theory Comput. Syst., 2009
Preface to Special Issue: Theory and Applications of Models of Computation (TAMC).
Math. Struct. Comput. Sci., 2009
Commun. Inf. Syst., 2009
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009
Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009
2008
SIGACT News, 2008
CoRR, 2008
Comput. Complex., 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
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
Theor. Comput. Sci., 2007
J. Comput. Syst. Sci., 2007
Electron. Colloquium Comput. Complex., 2007
Electron. Colloquium Comput. Complex., 2007
Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007
2006
Theory Comput. Syst., 2006
J. Comb. Optim., 2006
Electron. Colloquium Comput. Complex., 2006
Electron. Colloquium Comput. Complex., 2006
Electron. Colloquium Comput. Complex., 2006
Algorithmica, 2006
2005
J. Comput. Sci. Technol., 2005
Inf. Comput., 2005
Simulating Undirected <i>st</i>Connectivity Algorithms on Uniform JAGs and NNJAGs.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005
2004
SIAM J. Comput., 2004
Inf. Process. Lett., 2004
Inf. Process. Lett., 2004
Int. J. Found. Comput. Sci., 2004
Proceedings of the 4th IEEE International Conference on Data Mining (ICDM 2004), 2004
2003
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
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
Proceedings of the 19th International Conference on Data Engineering, 2003
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
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002
2001
Electron. Colloquium Comput. Complex., 2001
Electron. Colloquium Comput. Complex., 2001
Proceedings of the Twentieth ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems, 2001
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
2000
Theor. Comput. Sci., 2000
SIAM J. Comput., 2000
A note on the nonNPhardness of approximate lattice problems under general Cook reductions.
Inf. Process. Lett., 2000
Proceedings of the Algorithms and Computation, 11th International Conference, 2000
Proceedings of the Algorithmic Number Theory, 4th International Symposium, 2000
1999
SIAM J. Comput., 1999
Theory Comput. Syst., 1999
J. Comput. Syst. Sci., 1999
Approximating the SVP to within a Factor (1+1/dim<sup>xi</sup>) 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
Inf. Comput., 1999
Electron. Colloquium Comput. Complex., 1999
Electron. Colloquium Comput. Complex., 1999
Algorithmica, 1999
Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
Proceedings of the STACS 99, 1999
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999
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
Theory Comput. Syst., 1998
Efficient Algorithms for a Scheduling Problem and its Applications to Illicit Drug Market Crackdowns.
J. Comb. Optim., 1998
J. Complex., 1998
Electron. Colloquium Comput. Complex., 1998
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998
1997
Approximating the SVP to within a factor (1 + 1/dim<sup>epsilon</sup>) is NPhard under randomized reductions
Electron. Colloquium Comput. Complex., 1997
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997
Proceedings of the Computing and Combinatorics, Third Annual International Conference, 1997
1996
Math. Syst. Theory, 1996
Math. Syst. Theory, 1996
Proceedings of the STACS 96, 1996
Proceedings of the Seventh Annual ACMSIAM Symposium on Discrete Algorithms, 1996
1995
Random Struct. Algorithms, 1995
Electron. Colloquium Comput. Complex., 1995
Electron. Colloquium Comput. Complex., 1995
Proceedings of the STACS 95, 1995
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995
1994
SIAM J. Comput., 1994
On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line.
J. Comput. Syst. Sci., 1994
J. Comput. Syst. Sci., 1994
Int. J. Found. Comput. Sci., 1994
Electron. Colloquium Comput. Complex., 1994
Proceedings of the Fifth Annual ACMSIAM Symposium on Discrete Algorithms. 2325 January 1994, 1994
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
J. ACM, 1993
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, 1993
1992
Theor. Comput. Sci., 1992
Comb., 1992
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992
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
Inf. Process. Lett., 1991
Int. J. Found. Comput. Sci., 1991
Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991
1990
Inf. Comput., January, 1990
Math. Syst. Theory, 1990
Inf. Process. Lett., 1990
Proceedings of the STACS 90, 1990
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990
1989
Inf. Comput., July, 1989
SIAM J. Comput., 1989
With Probability One, a Random Oracle Separates PSPACE from the PolynomialTime Hierarchy.
J. Comput. Syst. Sci., 1989
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989
1988
SIAM J. Comput., 1988
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988
1987
SIAM J. Comput., 1987
Proceedings of the STACS 87, 1987
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
On Some Most Probable Separations of Complexity Classes.
PhD thesis, 1986
Proceedings of the Structure in Complexity Theory, 1986