!!Jin-Yi Cai - Selected Publications
\\
1. Jin-Yi Cai and Zhiguo Fu: Holographic Algorithm with Matchgates Is Universal for Planar #CSP Over Boolean Domain.\\
STOC 2017: 842-855. Full version available at [http://arxiv.org/abs/1603.07046] (94 pages).\\
\\
2. Jin-Yi Cai, Zhiguo Fu, Heng Guo and Tyson Williams: A Holant Dichotomy: Is the FKT Algorithm Universal?\\
In Proc. 56th IEEE Symposium on Foundations of Computer Science (FOCS) 2015: 1259-1276. Full version available at [http://arxiv.org/abs/1505.02993] (128 pages).\\
\\
3. Jin-Yi Cai, Heng Guo and Tyson Williams: The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. \\
In Proc. 55th IEEE Symposium on Foundations of Computer Science (FOCS) 2014: 601-610. \\
Full version in Research in the Mathematical Sciences (2016) 3:18 DOI 10.1186/s40687-016-0067-8 (77 pages).\\
\\
4. Jin-Yi Cai, Xi Chen, Pinyan Lu: Graph Homomorphisms with Complex Values: A Dichotomy Theorem.\\
SIAM J. Comput. 42(3): 924-1029 (2013) (106 pages).\\
\\
5. Jin-Yi Cai, Xi Chen: Complexity of Counting CSP with Complex Weights.\\
ACM Symposium on the Theory of Computing (STOC) 2012: 909-920. J. ACM 64(3): 19:1-19:39 (2017)\\
\\
6. Jin-Yi Cai, Pinyan Lu: Holographic Algorithms: The Power of Dimensionality Resolved.\\
International Colloquium on Automata, Languages and Programming (ICALP) 2007. LNCS 4596, pp. 631-642.\\
Best Paper Award.  Theor. Comput. Sci. 410(18): 1618-1628 (2009).\\
\\
7. Jin-Yi Cai, Pinyan Lu: Holographic Algorithms: From Art to Science.\\
J. Comput. Syst. Sci. 77(1): 41-61 (2011).  Preliminary version in STOC 2007, 401-410.\\
\\
8. Jin-Yi Cai , D. Sivakumar.  Sparse Hard sets for P: Resolution of a Conjecture of Hartmanis.\\
J. Comput. Syst. Sci. 58: 280--296 (1999). Preliminary version in FOCS 1995, 362--371.\\
\\
9. Jin-Yi Cai, Martin Furer, Neil Immerman.  An Optimal Lower Bound on the Number of Variables for Graph Identification.\\
Combinatorica, 12 (4):  389--410 (1992). Preliminary version in FOCS 1989, 612--617.\\
\\
10. Jin-Yi Cai.  With Probability One, a Random Oracle Separates PSPACE from the Polynomial-time Hierarchy.\\
J. Comput. Syst. Sci.  38 (1): 68--85 (1989).  Preliminary version in STOC 1986, 21--29.\\
\\
[List of publications|http://pages.cs.wisc.edu/~jyc/Some-Publications.pdf]