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