Jin-Yi Cai - RankMe

316 papers A* 53A 24B 13C 9Misc 15Journal 179Unranked 18

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Dichotomy for Holant* problems with one ternary function on domain size 3. Inf. Comput. Jin-Yi Cai, Pinyan Lu, Mingji Xia
2026	J	`jnl`	New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model. CoRR Austen Z. Fan, Jin-Yi Cai, Shuai Shao, Zhuxiao Tang
2026	J	`jnl`	Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups. CoRR Jin-Yi Cai, Ashwin Maran, Ben Young
2026	A	`conf`	Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem. ITCS Jin-Yi Cai, Ben Young
2025	A*	`conf`	Holant* Dichotomy on Domain Size 3: A Geometric Perspective. ICALP Jin-Yi Cai, Jin Soo Ihm
2025	J	`jnl`	Holant* Dichotomy on Domain Size 3: A Geometric Perspective. CoRR Jin-Yi Cai, Jin Soo Ihm
2025	J	`jnl`	Quantum Algorithms for Discrete Log Require Precise Rotations. ACM Trans. Quantum Comput. Jin-Yi Cai, Ben Young
2025	J	`jnl`	Restricted holant dichotomy on domain sizes 3 and 4. Theor. Comput. Sci. Yin Liu, Austen Z. Fan, Jin-Yi Cai
2025	J	`jnl`	The Battling Influencers Game: Nash Equilibria Structure of a Potential Game and Implications to Value Alignment. CoRR Young Wu, Yancheng Zhu, Jin-Yi Cai, Xiaojin Zhu
2025	J	`jnl`	Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem. CoRR Jin-Yi Cai, Ben Young
2024	J	`jnl`	A Uniformly Random Solution to Algorithmic Redistricting. CoRR Jin-Yi Cai, Jacob Kruse, Kenneth Mayer, Daniel P. Szabo
2024	J	`jnl`	Bounded Degree Nonnegative Counting CSP. ACM Trans. Comput. Theory Jin-Yi Cai, Daniel P. Szabo
2024	J	`jnl`	Counting Cycles on Planar Graphs in Subexponential Time. Algorithmica Jin-Yi Cai, Ashwin Maran
2024	J	`jnl`	Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint. ACM Trans. Comput. Theory Jin-Yi Cai, Ben Young
2024	J	`jnl`	Polynomial and analytic methods for classifying complexity of planar graph homomorphisms. CoRR Jin-Yi Cai, Ashwin Maran
2024	J	`jnl`	Shor's algorithm does not factor large integers in the presence of noise. Sci. China Inf. Sci. Jin-Yi Cai
2023	J	`jnl`	A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory. Comput. Complex. Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, Michael Kowalczyk
2023	J	`jnl`	A dichotomy for bounded degree graph homomorphisms with nonnegative weights. J. Comput. Syst. Sci. Artem Govorov, Jin-Yi Cai, Martin E. Dyer
2023	J	`jnl`	Bipartite 3-regular counting problems with mixed signs. J. Comput. Syst. Sci. Jin-Yi Cai, Austen Z. Fan, Yin Liu
2023	J	`jnl`	Complexity classification of the eight-vertex model. Inf. Comput. Jin-Yi Cai, Zhiguo Fu
2023	J	`jnl`	Dichotomy result on 3-regular bipartite non-negative functions. Theor. Comput. Sci. Austen Z. Fan, Jin-Yi Cai
2023	J	`jnl`	Holographic Algorithms on Domains of General Size. Theory Comput. Syst. Zhiguo Fu, Jin-Yi Cai
2023	A*	`conf`	Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint. ICALP Jin-Yi Cai, Ben Young
2023	J	`jnl`	Planar 3-way Edge Perfect Matching Leads to A Holant Dichotomy. CoRR Jin-Yi Cai, Austen Z. Fan
2023	A*	`conf`	Properties of Position Matrices and Their Elections. AAAI Niclas Boehmer, Jin-Yi Cai, Piotr Faliszewski, Austen Z. Fan, Lukasz Janeczko, Andrzej Kaczmarczyk, Tomasz Was
2023	J	`jnl`	Properties of Position Matrices and Their Elections. CoRR Niclas Boehmer, Jin-Yi Cai, Piotr Faliszewski, Austen Z. Fan, Lukasz Janeczko, Andrzej Kaczmarczyk, Tomasz Was
2023	—	`conf`	Restricted Holant Dichotomy on Domains 3 and 4. COCOA (2) Yin Liu, Austen Z. Fan, Jin-Yi Cai
2023	J	`jnl`	Restricted Holant Dichotomy on Domains 3 and 4. CoRR Yin Liu, Austen Z. Fan, Jin-Yi Cai
2023	J	`jnl`	Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise. CoRR Jin-Yi Cai
2023	A*	`conf`	The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3. STOC Jin-Yi Cai, Ashwin Maran
2023	J	`jnl`	The complexity of counting planar graph homomorphisms of domain size 3. CoRR Jin-Yi Cai, Ashwin Maran
2022	B	`conf`	Bounded Degree Nonnegative Counting CSP. MFCS Jin-Yi Cai, Daniel P. Szabo
2022	Misc	`conf`	Counting Cycles on Planar Graphs in Subexponential Time. COCOON Jin-Yi Cai, Ashwin Maran
2022	J	`jnl`	Counting Cycles on Planar Graphs in Subexponential Time. CoRR Jin-Yi Cai, Ashwin Maran
2022	J	`jnl`	FKT is Not Universal - A Planar Holant Dichotomy for Symmetric Constraints. Theory Comput. Syst. Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams
2022	J	`jnl`	Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain. SIAM J. Comput. Jin-Yi Cai, Zhiguo Fu
2022	J	`jnl`	Perfect matchings, rank of connection tensors and graph homomorphisms. Comb. Probab. Comput. Jin-Yi Cai, Artem Govorov
2022	J	`jnl`	Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint. CoRR Jin-Yi Cai, Ben Young
2021	A*	`conf`	An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures. SODA Jin-Yi Cai, Tianyu Liu
2021	B	`conf`	Bipartite 3-Regular Counting Problems with Mixed Signs. FCT Jin-Yi Cai, Austen Z. Fan, Yin Liu
2021	J	`jnl`	Bipartite 3-Regular Counting Problems with Mixed Signs. CoRR Jin-Yi Cai, Austen Z. Fan, Yin Liu
2021	Misc	`conf`	Dichotomy Result on 3-Regular Bipartite Non-negative Functions. CSR Austen Z. Fan, Jin-Yi Cai
2021	A*	`conf`	New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification. SODA Jin-Yi Cai, Zhiguo Fu, Shuai Shao
2021	J	`jnl`	On a Theorem of Lovász that (&sdot, ACM Trans. Comput. Theory Jin-Yi Cai, Artem Govorov
2021	J	`jnl`	The complexity of counting edge colorings for simple graphs. Theor. Comput. Sci. Jin-Yi Cai, Artem Govorov
2020	A*	`conf`	A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights. ICALP Artem Govorov, Jin-Yi Cai, Martin E. Dyer
2020	A*	`conf`	A Dichotomy for Real Boolean Holant Problems. FOCS Shuai Shao, Jin-Yi Cai
2020	J	`jnl`	A Dichotomy for Real Boolean Holant Problems. CoRR Shuai Shao, Jin-Yi Cai
2020	J	`jnl`	A dichotomy for bounded degree graph homomorphisms with nonnegative weights. CoRR Artem Govorov, Jin-Yi Cai, Martin E. Dyer
2020	A	`conf`	Approximability of the Eight-Vertex Model. CCC Jin-Yi Cai, Tianyu Liu, Pinyan Lu, Jing Yu
2020	J	`jnl`	Beyond #CSP: A dichotomy for counting weighted Eulerian orientations with ARS. Inf. Comput. Jin-Yi Cai, Zhiguo Fu, Shuai Shao
2020	A*	`conf`	Counting Perfect Matchings and the Eight-Vertex Model. ICALP Jin-Yi Cai, Tianyu Liu
2020	J	`jnl`	Dichotomy Result on 3-Regular Bipartite Non-negative Functions. CoRR Austen Z. Fan, Jin-Yi Cai
2020	A*	`conf`	Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs. FOCS Jin-Yi Cai, Artem Govorov
2020	J	`jnl`	Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs. CoRR Jin-Yi Cai, Artem Govorov
2020	J	`jnl`	Dichotomy for Holant Theory Comput. Syst. Jin-Yi Cai, Pinyan Lu, Mingji Xia
2020	J	`jnl`	FPRAS via MCMC where it mixes torpidly (and very little effort). CoRR Jin-Yi Cai, Tianyu Liu
2020	A*	`conf`	From Holant to Quantum Entanglement and Back. ICALP Jin-Yi Cai, Zhiguo Fu, Shuai Shao
2020	J	`jnl`	From Holant to Quantum Entanglement and Back. CoRR Jin-Yi Cai, Zhiguo Fu, Shuai Shao
2020	A	`conf`	On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H. ITCS Jin-Yi Cai, Artem Govorov
2020	J	`jnl`	The Complexity of Counting Edge Colorings for Simple Graphs. CoRR Jin-Yi Cai, Artem Govorov
2019	J	`jnl`	A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. Comput. Complex. Jin-Yi Cai, Xi Chen
2019	A*	`conf`	Approximability of the Six-vertex Model. SODA Jin-Yi Cai, Tianyu Liu, Pinyan Lu
2019	J	`jnl`	Complexity of Counting Weighted Eulerian Orientations with ARS. CoRR Jin-Yi Cai, Zhiguo Fu, Shuai Shao
2019	J	`jnl`	Counting perfect matchings and the eight-vertex model. CoRR Jin-Yi Cai, Tianyu Liu
2019	J	`jnl`	Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy. ACM Trans. Comput. Theory Jin-Yi Cai, Michael Kowalczyk, Tyson Williams
2019	J	`jnl`	On a Theorem of Lovász that hom(·, H) Determines the Isomorhphism Type of H. CoRR Jin-Yi Cai, Artem Govorov
2019	A*	`conf`	Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms. SODA Jin-Yi Cai, Artem Govorov
2019	J	`jnl`	Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms. CoRR Jin-Yi Cai, Artem Govorov
2018	A	`conf`	A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory. ITCS Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, Michael Kowalczyk
2018	J	`jnl`	Approximability of the Eight-vertex Model. CoRR Jin-Yi Cai, Tianyu Liu, Pinyan Lu, Jing Yu
2018	J	`jnl`	Clifford gates in the Holant framework. Theor. Comput. Sci. Jin-Yi Cai, Heng Guo, Tyson Williams
2018	J	`jnl`	Complexity classification of the six-vertex model. Inf. Comput. Jin-Yi Cai, Zhiguo Fu, Mingji Xia
2018	A*	`conf`	Dichotomy for Real Holant SODA Jin-Yi Cai, Pinyan Lu, Mingji Xia
2018	J	`jnl`	Holographic algorithms beyond matchgates. Inf. Comput. Jin-Yi Cai, Heng Guo, Tyson Williams
2017	J	`jnl`	A Complexity Trichotomy for the Six-Vertex Model. CoRR Jin-Yi Cai, Zhiguo Fu, Shuai Shao
2017	J	`jnl`	Approximability of the Six-vertex Model. CoRR Jin-Yi Cai, Tianyu Liu, Pinyan Lu
2017	J	`jnl`	Clifford Gates in the Holant Framework. CoRR Jin-Yi Cai, Heng Guo, Tyson Williams
2017	J	`jnl`	Complexity Classification Of The Six-Vertex Model. CoRR Jin-Yi Cai, Zhiguo Fu, Mingji Xia
2017	J	`jnl`	Complexity Classification of the Eight-Vertex Model. CoRR Jin-Yi Cai, Zhiguo Fu
2017	J	`jnl`	Complexity of Counting CSP with Complex Weights. J. ACM Jin-Yi Cai, Xi Chen
2017	J	`jnl`	Dichotomy for Real Holant CoRR Jin-Yi Cai, Pinyan Lu, Mingji Xia
2017	J	`jnl`	Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. SIAM J. Comput. Jin-Yi Cai, Pinyan Lu, Mingji Xia
2017	A*	`conf`	Holographic algorithm with matchgates is universal for planar #CSP over boolean domain. STOC Jin-Yi Cai, Zhiguo Fu
2016	J	`jnl`	#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. J. Comput. Syst. Sci. Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, Eric Vigoda
2016	J	`jnl`	A Complete Dichotomy Rises from the Capture of Vanishing Signatures. SIAM J. Comput. Jin-Yi Cai, Heng Guo, Tyson Williams
2016	—	`ch.`	Complexity Dichotomies for Counting Graph Homomorphisms. Encyclopedia of Algorithms Jin-Yi Cai, Xi Chen, Pinyan Lu
2016	J	`jnl`	Erratum to: Signature Theory in Holographic Algorithms. Algorithmica Jin-Yi Cai, Pinyan Lu
2016	J	`jnl`	Holant Problems for 3-Regular Graphs with Complex Edge Functions. Theory Comput. Syst. Michael Kowalczyk, Jin-Yi Cai
2016	—	`ch.`	Holant Problems. Encyclopedia of Algorithms Jin-Yi Cai, Heng Guo, Tyson Williams
2016	J	`jnl`	Holographic Algorithm with Matchgates Is Universal for Planar $\#$CSP Over Boolean Domain. CoRR Jin-Yi Cai, Zhiguo Fu
2016	—	`ch.`	Holographic Algorithms. Encyclopedia of Algorithms Jin-Yi Cai, Pinyan Lu, Mingji Xia
2016	J	`jnl`	Nonnegative Weighted #CSP: An Effective Complexity Dichotomy. SIAM J. Comput. Jin-Yi Cai, Xi Chen, Pinyan Lu
2015	A*	`conf`	A Holant Dichotomy: Is the FKT Algorithm Universal? FOCS Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams
2015	J	`jnl`	A Holant Dichotomy: Is the FKT Algorithm Universal? CoRR Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams
2014	—	`conf`	#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. APPROX-RANDOM Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, Eric Vigoda
2014	J	`jnl`	A collapse theorem for holographic algorithms with matchgates on domain size at most 4. Inf. Comput. Jin-Yi Cai, Zhiguo Fu
2014	—	`conf`	Holographic Algorithms Beyond Matchgates. ICALP (1) Jin-Yi Cai, Heng Guo, Tyson Williams
2014	J	`jnl`	Matchgates Revisited. Theory Comput. Jin-Yi Cai, Aaron Gorenstein
2014	A*	`conf`	The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. FOCS Jin-Yi Cai, Heng Guo, Tyson Williams
2014	J	`jnl`	The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. CoRR Jin-Yi Cai, Heng Guo, Tyson Williams
2014	J	`jnl`	The complexity of complex weighted Boolean #CSP. J. Comput. Syst. Sci. Jin-Yi Cai, Pinyan Lu, Mingji Xia
2013	J	`jnl`	A Collapse Theorem for Holographic Algorithms with Matchgates on Domain Size at Most 4 CoRR Jin-Yi Cai, Zhiguo Fu
2013	A*	`conf`	A complete dichotomy rises from the capture of vanishing signatures: extended abstract. STOC Jin-Yi Cai, Heng Guo, Tyson Williams
2013	J	`jnl`	Approximating the Partition Function of Two-Spin Systems on Bipartite Graphs. CoRR Jin-Yi Cai, Leslie Ann Goldberg, Heng Guo, Mark Jerrum
2013	C	`conf`	Complexity Dichotomy for Counting Problems. LATA Jin-Yi Cai
2013	A*	`conf`	Dichotomy for Holant* Problems with Domain Size 3. SODA Jin-Yi Cai, Pinyan Lu, Mingji Xia
2013	J	`jnl`	Graph Homomorphisms with Complex Values: A Dichotomy Theorem. SIAM J. Comput. Jin-Yi Cai, Xi Chen, Pinyan Lu
2013	J	`jnl`	Holographic Algorithms Beyond Matchgates. CoRR Jin-Yi Cai, Heng Guo, Tyson Williams
2013	J	`jnl`	Matchgates Revisited CoRR Jin-Yi Cai, Aaron Gorenstein
2013	J	`jnl`	Matchgates Revisited. Electron. Colloquium Comput. Complex. Jin-Yi Cai, Aaron Gorenstein
2013	A	`conf`	On optimal differentially private mechanisms for count-range queries. ICDT Chen Zeng, Jin-Yi Cai, Pinyan Lu, Jeffrey F. Naughton
2013	J	`jnl`	Partition functions on Theor. Comput. Sci. Jin-Yi Cai, Michael Kowalczyk
2013	J	`jnl`	The Minimum Consistent Subset Cover Problem: A Minimization View of Data Mining. IEEE Trans. Knowl. Data Eng. Byron J. Gao, Martin Ester, Hui Xiong, Jin-Yi Cai, Oliver Schulte
2012	J	`jnl`	A Complete Dichotomy Rises from the Capture of Vanishing Signatures CoRR Jin-Yi Cai, Heng Guo, Tyson Williams
2012	A*	`conf`	Complexity of counting CSP with complex weights. STOC Jin-Yi Cai, Xi Chen
2012	J	`jnl`	Dichotomy for Holant* Problems with a Function on Domain Size 3 CoRR Jin-Yi Cai, Pinyan Lu, Mingji Xia
2012	J	`jnl`	From Holant to #CSP and Back: Dichotomy for Holant c Problems. Algorithmica Jin-Yi Cai, Sangxia Huang, Pinyan Lu
2012	A	`conf`	Gadgets and anti-gadgets leading to a complexity dichotomy. ITCS Jin-Yi Cai, Michael Kowalczyk, Tyson Williams
2012	C	`conf`	Holographic Algorithms on Domain Size k > 2. TAMC Zhiguo Fu, Jin-Yi Cai
2012	J	`jnl`	Holographic reduction, interpolation and hardness. Comput. Complex. Jin-Yi Cai, Pinyan Lu, Mingji Xia
2012	J	`jnl`	Inapproximability After Uniqueness Phase Transition in Two-Spin Systems CoRR Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu
2012	C	`conf`	Inapproximability after Uniqueness Phase Transition in Two-Spin Systems. COCOA Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu
2012	J	`jnl`	On differentially private frequent itemset mining. Proc. VLDB Endow. Chen Zeng, Jeffrey F. Naughton, Jin-Yi Cai
2012	J	`jnl`	Spin systems on k-regular graphs with complex edge functions. Theor. Comput. Sci. Jin-Yi Cai, Michael Kowalczyk
2011	J	`jnl`	A computational proof of complexity of some restricted counting problems. Theor. Comput. Sci. Jin-Yi Cai, Pinyan Lu, Mingji Xia
2011	J	`jnl`	Approximation and hardness results for label cut and related problems. J. Comb. Optim. Peng Zhang, Jin-Yi Cai, Linqing Tang, Wenbo Zhao
2011	J	`jnl`	Complexity of Counting CSP with Complex Weights CoRR Jin-Yi Cai, Xi Chen
2011	J	`jnl`	Computational Complexity of Holant Problems. SIAM J. Comput. Jin-Yi Cai, Pinyan Lu, Mingji Xia
2011	A*	`conf`	Dichotomy for Holant* Problems of Boolean Domain. SODA Jin-Yi Cai, Pinyan Lu, Mingji Xia
2011	J	`jnl`	Foreword. J. Comput. Syst. Sci. Jin-Yi Cai, Alan L. Selman
2011	J	`jnl`	Gadgets and Anti-gadgets Leading to a Complexity Dichotomy CoRR Jin-Yi Cai, Michael Kowalczyk, Tyson Williams
2011	J	`jnl`	Holographic algorithms: From art to science. J. Comput. Syst. Sci. Jin-Yi Cai, Pinyan Lu
2011	J	`jnl`	Honeynet games: a game theoretic approach to defending network monitors. J. Comb. Optim. Jin-Yi Cai, Vinod Yegneswaran, Chris Alfeld, Paul Barford
2011	A	`conf`	Non-negatively Weighted #CSP: An Effective Complexity Dichotomy. CCC Jin-Yi Cai, Xi Chen, Pinyan Lu
2011	—	`conf`	Progress in Complexity of Counting Problems. FAW-AAIM Jin-Yi Cai
2011	J	`jnl`	Signature Theory in Holographic Algorithms. Algorithmica Jin-Yi Cai, Pinyan Lu
2011	Misc	`conf`	Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities. COCOON Jin-Yi Cai, Michael Kowalczyk
2010	J	`jnl`	A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights CoRR Jin-Yi Cai, Xi Chen
2010	A*	`conf`	A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights. FOCS Jin-Yi Cai, Xi Chen
2010	C	`conf`	A Dichotomy for TAMC Jin-Yi Cai, Michael Kowalczyk
2010	J	`jnl`	From Holant To #CSP And Back: Dichotomy For Holant$^c$ Problems CoRR Jin-Yi Cai, Sangxia Huang, Pinyan Lu
2010	—	`conf`	From Holant to #CSP and Back: Dichotomy for Holant ISAAC (1) Jin-Yi Cai, Sangxia Huang, Pinyan Lu
2010	—	`conf`	Graph Homomorphisms with Complex Values: A Dichotomy Theorem. ICALP (1) Jin-Yi Cai, Xi Chen, Pinyan Lu
2010	J	`jnl`	Holant Problems for Regular Graphs with Complex Edge Functions CoRR Michael Kowalczyk, Jin-Yi Cai
2010	A	`conf`	Holant Problems for Regular Graphs with Complex Edge Functions. STACS Michael Kowalczyk, Jin-Yi Cai
2010	J	`jnl`	Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP CoRR Jin-Yi Cai, Pinyan Lu, Mingji Xia
2010	A*	`conf`	Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP. FOCS Jin-Yi Cai, Pinyan Lu, Mingji Xia
2010	J	`jnl`	Non-negative Weighted #CSPs: An Effective Complexity Dichotomy CoRR Jin-Yi Cai, Xi Chen, Pinyan Lu
2010	J	`jnl`	On Symmetric Signatures in Holographic Algorithms. Theory Comput. Syst. Jin-Yi Cai, Pinyan Lu
2010	J	`jnl`	On Tractable Exponential Sums CoRR Jin-Yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu
2010	Misc	`conf`	On Tractable Exponential Sums. FAW Jin-Yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu
2010	J	`jnl`	On blockwise symmetric signatures for matchgates. Theor. Comput. Sci. Jin-Yi Cai, Pinyan Lu
2010	J	`jnl`	Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic. Comput. Complex. Jin-Yi Cai, Xi Chen, Dong Li
2009	C	`conf`	A Computational Proof of Complexity of Some Restricted Counting Problems. TAMC Jin-Yi Cai, Pinyan Lu, Mingji Xia
2009	J	`jnl`	A Novel Information Transmission Problem and its Optimal Solution. Commun. Inf. Syst. Eric Bach, Jin-Yi Cai
2009	Misc	`conf`	An Attacker-Defender Game for Honeynets. COCOON Jin-Yi Cai, Vinod Yegneswaran, Chris Alfeld, Paul Barford
2009	C	`conf`	Approximation and Hardness Results for Label Cut and Related Problems. TAMC Peng Zhang, Jin-Yi Cai, Linqing Tang, Wenbo Zhao
2009	J	`jnl`	Graph Homomorphisms with Complex Values: A Dichotomy Theorem CoRR Jin-Yi Cai, Xi Chen, Pinyan Lu
2009	A*	`conf`	Holant problems and counting CSP. STOC Jin-Yi Cai, Pinyan Lu, Mingji Xia
2009	J	`jnl`	Holographic algorithms: The power of dimensionality resolved. Theor. Comput. Sci. Jin-Yi Cai, Pinyan Lu
2009	J	`jnl`	On the Theory of Matchgate Computations. Theory Comput. Syst. Jin-Yi Cai, Vinay Choudhary, Pinyan Lu
2009	J	`jnl`	Preface to Special Issue: Theory and Applications of Models of Computation (TAMC). Math. Struct. Comput. Sci. Jin-Yi Cai, S. Barry Cooper, Angsheng Li
2008	J	`jnl`	A Family of Counter Examples to an Approach to Graph Isomorphism CoRR Jin-Yi Cai, Pinyan Lu, Mingji Xia
2008	A*	`conf`	A quadratic lower bound for the permanent and determinant problem over any characteristic != 2. STOC Jin-Yi Cai, Xi Chen, Dong Li
2008	J	`jnl`	Basis Collapse in Holographic Algorithms. Comput. Complex. Jin-Yi Cai, Pinyan Lu
2008	A*	`conf`	Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. FOCS Jin-Yi Cai, Pinyan Lu, Mingji Xia
2008	A*	`conf`	Holographic algorithms with unsymmetric signatures. SODA Jin-Yi Cai, Pinyan Lu
2008	J	`jnl`	Holographic algorithms: guest column. SIGACT News Jin-Yi Cai
2008	B	`conf`	Signature Theory in Holographic Algorithms. ISAAC Jin-Yi Cai, Pinyan Lu
2007	B	`conf`	A Novel Information Transmission Problem and Its Optimal Solution. FCT Eric Bach, Jin-Yi Cai
2007	A	`conf`	Bases Collapse in Holographic Algorithms. CCC Jin-Yi Cai, Pinyan Lu
2007	J	`jnl`	Bases Collapse in Holographic Algorithms. Electron. Colloquium Comput. Complex. Jin-Yi Cai, Pinyan Lu
2007	A*	`conf`	Holographic Algorithms: The Power of Dimensionality Resolved. ICALP Jin-Yi Cai, Pinyan Lu
2007	J	`jnl`	Holographic Algorithms: The Power of Dimensionality Resolved. Electron. Colloquium Comput. Complex. Jin-Yi Cai, Pinyan Lu
2007	A*	`conf`	Holographic algorithms: from art to science. STOC Jin-Yi Cai, Pinyan Lu
2007	B	`conf`	On Block-Wise Symmetric Signatures for Matchgates. FCT Jin-Yi Cai, Pinyan Lu
2007	J	`jnl`	On Block-wise Symmetric Signatures for Matchgates. Electron. Colloquium Comput. Complex. Jin-Yi Cai, Pinyan Lu
2007	A	`conf`	On Symmetric Signatures in Holographic Algorithms. STACS Jin-Yi Cai, Pinyan Lu
2007	A	`conf`	On the Theory of Matchgate Computations. CCC Jin-Yi Cai, Vinay Choudhary, Pinyan Lu
2007	J	`jnl`	S J. Comput. Syst. Sci. Jin-Yi Cai
2007	J	`jnl`	Some Results on Matchgates and Holographic Algorithms. Int. J. Softw. Informatics Jin-Yi Cai, Vinay Choudhary
2007	A*	`conf`	The minimum consistent subset cover problem and its applications in data mining. KDD Byron J. Gao, Martin Ester, Jin-Yi Cai, Oliver Schulte, Hui Xiong
2007	C	`ed.`	Theory and Applications of Models of Computation, 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, Proceedings TAMC Jin-Yi Cai, S. Barry Cooper, Hong Zhu
2007	J	`jnl`	Valiant's Holant Theorem and matchgate tensors. Theor. Comput. Sci. Jin-Yi Cai, Vinay Choudhary
2006	J	`jnl`	Holographic Algorithms: From Art to Science. Electron. Colloquium Comput. Complex. Jin-Yi Cai, Pinyan Lu
2006	J	`jnl`	On Symmetric Signatures in Holographic Algorithms. Electron. Colloquium Comput. Complex. Jin-Yi Cai, Pinyan Lu
2006	J	`jnl`	On the Theory of Matchgate Computations Electron. Colloquium Comput. Complex. Jin-Yi Cai, Vinay Choudhary
2006	J	`jnl`	On zero error algorithms having oracle access to one query. J. Comb. Optim. Jin-Yi Cai, Venkatesan T. Chakaravarthy
2006	J	`jnl`	Random Access to Advice Strings and Collapsing Results. Algorithmica Jin-Yi Cai, Osamu Watanabe
2006	—	`conf`	Some Results on Matchgates and Holographic Algorithms. ICALP (1) Jin-Yi Cai, Vinay Choudhary
2006	J	`jnl`	Some Results on Matchgates and Holographic Algorithms. Electron. Colloquium Comput. Complex. Jin-Yi Cai, Vinay Choudhary
2006	C	`ed.`	Theory and Applications of Models of Computation, Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006, Proceedings TAMC Jin-Yi Cai, S. Barry Cooper, Angsheng Li
2006	J	`jnl`	Time-Space Tradeoff in Derandomizing Probabilistic Logspace. Theory Comput. Syst. Jin-Yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek
2006	C	`conf`	Valiant's Holant Theorem and Matchgate Tensors. TAMC Jin-Yi Cai, Vinay Choudhary
2005	Misc	`conf`	A Note on Zero Error Algorithms Having Oracle Access to One NP Query. COCOON Jin-Yi Cai, Venkatesan T. Chakaravarthy
2005	J	`jnl`	Competing provers yield improved Karp-Lipton collapse results. Inf. Comput. Jin-Yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara
2005	J	`jnl`	Progress in Computational Complexity Theory. J. Comput. Sci. Technol. Jin-Yi Cai, Hong Zhu
2005	B	`conf`	Simulating Undirected ISAAC Pinyan Lu, Jialin Zhang, Chung Keung Poon, Jin-Yi Cai
2005	J	`jnl`	Valiant's Holant Theorem and Matchgate Tensors Electron. Colloquium Comput. Complex. Jin-Yi Cai, Vinay Choudhary
2004	J	`jnl`	A note on quadratic residuosity and UP. Inf. Process. Lett. Jin-Yi Cai, Robert A. Threlfall
2004	A*	`conf`	Mass Spectrum Labeling: Theory and Practice. ICDM Zheng Huang, Lei Chen, Jin-Yi Cai, Deborah S. Gross, David R. Musicant, Raghu Ramakrishnan, James J. Schauer, Stephen J. Wright
2004	J	`jnl`	On Higher Arthur-Merlin Classes. Int. J. Found. Comput. Sci. Jin-Yi Cai, Denis Charles, Aduri Pavan, Samik Sengupta
2004	J	`jnl`	On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy. SIAM J. Comput. Jin-Yi Cai, Osamu Watanabe
2004	B	`conf`	Random Access to Advice Strings and Collapsing Results. ISAAC Jin-Yi Cai, Osamu Watanabe
2004	J	`jnl`	Relativized collapsing between BPP and PH under stringent oracle access. Inf. Process. Lett. Jin-Yi Cai, Osamu Watanabe
2004	A	`conf`	Time-Space Tradeoff in Derandomizing Probabilistic Logspace. STACS Jin-Yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek
2003	J	`jnl`	A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor. Discret. Appl. Math. Jin-Yi Cai
2003	A	`conf`	Competing Provers Yield Improved Karp-Lipton Collapse Results. STACS Jin-Yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara
2003	J	`jnl`	Essentially Every Unimodular Matrix Defines an Expander. Theory Comput. Syst. Jin-Yi Cai
2003	A*	`conf`	Estimation of Congestion Price Using Probabilistic Packet Marking. INFOCOM Micah Adler, Jin-Yi Cai, Jonathan K. Shapiro, Donald F. Towsley
2003	Misc	`conf`	On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results. COCOON Jin-Yi Cai, Osamu Watanabe
2003	J	`jnl`	On testing for zero polynomials by a set of points with bounded precision. Theor. Comput. Sci. Jin-Yi Cai, Eric Bach
2003	—	`conf`	Stringent Relativization. FSTTCS Jin-Yi Cai, Osamu Watanabe
2003	A*	`conf`	X-Diff: An Effective Change Detection Algorithm for XML Documents. ICDE Yuan Wang, David J. DeWitt, Jin-Yi Cai
2002	Misc	`conf`	On Higher Arthur-Merlin Classes. COCOON Jin-Yi Cai, Denis Charles, Aduri Pavan, Samik Sengupta
2002	B	`conf`	On the Minimum Volume of a Perturbed Unit Cube. ISAAC Jin-Yi Cai
2001	J	`jnl`	Essentially every unimodular matrix defines an expander Electron. Colloquium Comput. Complex. Jin-Yi Cai
2001	Misc	`conf`	On Testing for Zero Polynomials by a Set of Points with Bounded Precision. COCOON Jin-Yi Cai, Eric Bach
2001	A*	`conf`	On the Average-Case Hardness of CVP. FOCS Jin-Yi Cai
2001	A*	`conf`	On the Complexity of Join Predicates. PODS Jin-Yi Cai, Venkatesan T. Chakaravarthy, Raghav Kaushik, Jeffrey F. Naughton
2001	A*	`conf`	S FOCS Jin-Yi Cai
2001	J	`jnl`	S_2 Electron. Colloquium Comput. Complex. Jin-Yi Cai
2000	J	`jnl`	A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. Inf. Process. Lett. Jin-Yi Cai, Ajay Nerurkar
2000	A*	`conf`	Circuit minimization problem. STOC Valentine Kabanets, Jin-Yi Cai
2000	B	`conf`	Essentially Every Unimodular Matrix Defines and Expander. ISAAC Jin-Yi Cai
2000	J	`jnl`	Resolution of Hartmanis' conjecture for NL-hard sparse sets. Theor. Comput. Sci. Jin-Yi Cai, D. Sivakumar
2000	—	`conf`	The Complexity of Some Lattice Problems. ANTS Jin-Yi Cai
2000	J	`jnl`	The Complexity of the A B C Problem. SIAM J. Comput. Jin-Yi Cai, Richard J. Lipton, Yechezkel Zalcstein
1999	J	`jnl`	A Classification of the Probabilistic Polynomial Time Hierarchy Under Fault Tolerant Access to Oracle Classes. Inf. Process. Lett. Jin-Yi Cai
1999	J	`jnl`	A Lattice-Based Public-Key Cryptosystem. Inf. Comput. Jin-Yi Cai, Thomas W. Cusick
1999	Misc	`conf`	A New Transference Theorem in the Geometry of Numbers. COCOON Jin-Yi Cai
1999	A	`conf`	Applications of a New Transference Theorem to Ajtai's Connection Factor. CCC Jin-Yi Cai
1999	J	`jnl`	Approximating the SVP to within a Factor (1+1/dim J. Comput. Syst. Sci. Jin-Yi Cai, Ajay Nerurkar
1999	J	`jnl`	Circuit Minimization Problem Electron. Colloquium Comput. Complex. Valentine Kabanets, Jin-Yi Cai
1999	J	`jnl`	Fine Separation of Average-Time Complexity Classes. SIAM J. Comput. Jin-Yi Cai, Alan L. Selman
1999	J	`jnl`	Foreword. Algorithmica Jin-Yi Cai, C. K. Wong
1999	A*	`conf`	Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. STOC Jin-Yi Cai, Ajay Nerurkar, D. Sivakumar
1999	Misc	`conf`	On Routing in Circulant Graphs. COCOON Jin-Yi Cai, George Havas, Bernard Mans, Ajay Nerurkar, Jean-Pierre Seifert, Igor E. Shparlinski
1999	A	`conf`	On the Hardness of Permanent. STACS Jin-Yi Cai, Aduri Pavan, D. Sivakumar
1999	J	`jnl`	Robust Reductions CoRR Jin-Yi Cai, Lane A. Hemaspaandra, Gerd Wechsung
1999	J	`jnl`	Robust Reductions. Theory Comput. Syst. Jin-Yi Cai, Lane A. Hemaspaandra, Gerd Wechsung
1999	J	`jnl`	Some Recent Progress on the Complexity of Lattice Problems Electron. Colloquium Comput. Complex. Jin-Yi Cai
1999	A	`conf`	Some Recent Progress on the Complexity of Lattice Problems. CCC Jin-Yi Cai
1999	J	`jnl`	Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis. J. Comput. Syst. Sci. Jin-Yi Cai, D. Sivakumar
1998	B	`conf`	A Lattice-Based Public-Key Cryptosystem. Selected Areas in Cryptography Jin-Yi Cai, Thomas W. Cusick
1998	J	`jnl`	A Relation of Primal-Dual Lattices and the Complexity of Shortest Lattice Vector Problem. Theor. Comput. Sci. Jin-Yi Cai
1998	J	`jnl`	A new transference theorem and applications to Ajtai's connection factor Electron. Colloquium Comput. Complex. Jin-Yi Cai
1998	A	`conf`	Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions. CCC Jin-Yi Cai, Ajay Nerurkar
1998	J	`jnl`	Efficient Algorithms for a Scheduling Problem and its Applications to Illicit Drug Market Crackdowns. J. Comb. Optim. Pu Cai, Jin-Yi Cai, Ashish V. Naik
1998	J	`jnl`	Frobenius's Degree Formula and Toda's Polynomials. Theory Comput. Syst. Jin-Yi Cai
1998	J	`jnl`	On A Scheduling Problem of Time Deteriorating Jobs. J. Complex. Jin-Yi Cai, Pu Cai, Yixin Zhu
1998	Misc	`conf`	Robust Reductions. COCOON Jin-Yi Cai, Lane A. Hemaspaandra, Gerd Wechsung
1997	A*	`conf`	An Improved Worst-Case to Average-Case Connection for Lattice Problems. FOCS Jin-Yi Cai, Ajay Nerurkar
1997	J	`jnl`	Approximating the SVP to within a factor (1 + 1/dim Electron. Colloquium Comput. Complex. Jin-Yi Cai, Ajay Nerurkar
1997	A*	`conf`	Constant Depth Circuits and the Lutz Hypothesis. FOCS Jin-Yi Cai, D. Sivakumar, Martin Strauss
1997	Misc	`conf`	On the 100% Rule of Sensivity Analzsis in Linear Programming. COCOON Pu Cai, Jin-Yi Cai
1997	Misc	`conf`	Resolution of Hartmanis' Conjecture for NL-Hard Sparse Sets. COCOON Jin-Yi Cai, D. Sivakumar
1996	Misc	`ed.`	Computing and Combinatorics, Second Annual International Conference, COCOON '96, Hong Kong, June 17-19, 1996, Proceedings COCOON Jin-Yi Cai, C. K. Wong
1996	A	`conf`	Fine Separation of Average Time Complexity Classes. STACS Jin-Yi Cai, Alan L. Selman
1996	A*	`conf`	Multiplicative Equations over Commuting Matrices. SODA László Babai, Robert Beals, Jin-Yi Cai, Gábor Ivanyos, Eugene M. Luks
1996	J	`jnl`	On the Correlation of Symmetric Functions. Math. Syst. Theory Jin-Yi Cai, Frederic Green, Thomas Thierauf
1996	A	`conf`	On the Existence of Hard Sparse Sets under Weak Reductions. STACS Jin-Yi Cai, Ashish V. Naik, D. Sivakumar
1996	A	`ed.`	Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996 CCC Steven Homer, Jin-Yi Cai
1996	J	`jnl`	The Bounded Membership Problem of the Monoid SL_2(N). Math. Syst. Theory Jin-Yi Cai, Zicheng Liu
1995	J	`jnl`	Average Time Complexity Classes Electron. Colloquium Comput. Complex. Jin-Yi Cai, Alan L. Selman
1995	A	`conf`	Communication Complexity of Key Agreement on Small Ranges. STACS Jin-Yi Cai, Richard J. Lipton, Luc Longpré, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar
1995	J	`jnl`	On the Impossibility of Amplifying the Independence of Random Variables. Random Struct. Algorithms Jin-Yi Cai, Suresh Chari
1995	J	`jnl`	Pseudorandom Generators, Measure Theory, and Natural Proofs Electron. Colloquium Comput. Complex. Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai
1995	A*	`conf`	Pseudorandom Generators, Measure Theory, and Natural Proofs. FOCS Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai
1995	A*	`conf`	The Resolution of a Hartmanis Conjecture. FOCS Jin-Yi Cai, D. Sivakumar
1994	J	`jnl`	Computing Jordan Normal Forms Exactly for Commuting Matrices in Polynomial Time. Int. J. Found. Comput. Sci. Jin-Yi Cai
1994	A*	`conf`	Efficient Average-Case Algorithms for the Modular Group FOCS Jin-Yi Cai, Wolfgang H. J. Fuchs, Dexter Kozen, Zicheng Liu
1994	J	`jnl`	Efficient Average-Case Algorithms for the Modular Group Electron. Colloquium Comput. Complex. Jin-Yi Cai, Wolfgang H. J. Fuchs, Dexter Kozen, Zicheng Liu
1994	J	`jnl`	On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line. J. Comput. Syst. Sci. Jin-Yi Cai, Juris Hartmanis
1994	J	`jnl`	PSPACE Is Provable by Two Provers in One Round. J. Comput. Syst. Sci. Jin-Yi Cai, Anne Condon, Richard J. Lipton
1994	A*	`conf`	Reliable Benchmarks Using Numerical Instability. SODA Sigal Ar, Jin-Yi Cai
1994	B	`conf`	Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic Geometry. ISAAC Jin-Yi Cai, Michael D. Hirsch
1994	J	`jnl`	Subquadratic Simulations of Balanced Formulae by Branching Programs. SIAM J. Comput. Jin-Yi Cai, Richard J. Lipton
1994	A*	`conf`	The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices FOCS Jin-Yi Cai, Richard J. Lipton, Yechezkel Zalcstein
1993	—	`ed.`	Advances In Computational Complexity Theory, Proceedings of a DIMACS Workshop, New Jersey, USA, December 3-7, 1990 Advances In Computational Complexity Theory Jin-Yi Cai
1993	J	`jnl`	Taking Random Walks to Grow Trees in Hypercubes. J. ACM Sandeep N. Bhatt, Jin-Yi Cai
1993	—	`conf`	Towards Uncheatable benchmarks. SCT Jin-Yi Cai, Richard J. Lipton, Robert Sedgewick, Andrew Chi-Chih Yao
1992	J	`jnl`	An optimal lower bound on the number of variables for graph identification. Comb. Jin-Yi Cai, Martin Fürer, Neil Immerman
1992	J	`jnl`	On Games of Incomplete Information. Theor. Comput. Sci. Jin-Yi Cai, Anne Condon, Richard J. Lipton
1992	A*	`conf`	Parallel Computation Over Hyperbolic Groups STOC Jin-Yi Cai
1992	B	`conf`	Promise Problems and Access to Unambiguous Computation. MFCS Jin-Yi Cai, Lane A. Hemachandra, Jozef Vyskoc
1992	—	`conf`	Promise Problems and Guarded Access to Unambiguous Computation. Complexity Theory: Current Research Jin-Yi Cai, Lane A. Hemachandra, Jozef Vyskoc
1991	J	`jnl`	A Note on Enumarative Counting. Inf. Process. Lett. Jin-Yi Cai, Lane A. Hemachandra
1991	B	`conf`	Computations Over Infinite Groups. FCT Jin-Yi Cai
1991	—	`conf`	PSPACE Is Provable By Two Provers In One Round. SCT Jin-Yi Cai, Anne Condon, Richard J. Lipton
1991	J	`jnl`	PSPACE Survives Constant-Width Bottlenecks. Int. J. Found. Comput. Sci. Jin-Yi Cai, Merrick L. Furst
1990	J	`jnl`	A Note on the Determinant and Permanent Problem Inf. Comput. Jin-Yi Cai
1990	J	`jnl`	Lower Bounds for Constant-Depth Circuits in the Presence of Help Bits. Inf. Process. Lett. Jin-Yi Cai
1990	—	`conf`	On Bounded Round Multi-Prover Interactive Proof Systems. SCT Jin-Yi Cai, Anne Condon, Richard J. Lipton
1990	J	`jnl`	On the Power of Parity Polynomial Time. Math. Syst. Theory Jin-Yi Cai, Lane A. Hemachandra
1990	A	`conf`	Playing Games of Incomplete Information. STACS Jin-Yi Cai, Anne Condon, Richard J. Lipton
1989	A*	`conf`	An Optimal Lower Bound on the Number of Variables for Graph Identification FOCS Jin-Yi Cai, Martin Fürer, Neil Immerman
1989	J	`jnl`	Enumerative Counting Is Hard Inf. Comput. Jin-Yi Cai, Lane A. Hemachandra
1989	A*	`conf`	Lower Bounds for Constant Depth Circuits in the Presence of Help Bits FOCS Jin-Yi Cai
1989	A	`conf`	On the Power of Parity Polynomial Time. STACS Jin-Yi Cai, Lane A. Hemachandra
1989	A*	`conf`	Subquadratic Simulations of Circuits by Branching Programs FOCS Jin-Yi Cai, Richard J. Lipton
1989	J	`jnl`	The Boolean Hierarchy II: Applications. SIAM J. Comput. Jin-Yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung
1989	—	`conf`	The Complexity Of The Real Line Is A Fractal. SCT Jin-Yi Cai, Juris Hartmanis
1989	J	`jnl`	With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy. J. Comput. Syst. Sci. Jin-Yi Cai
1988	—	`conf`	Enumerative counting is hard. SCT Jin-Yi Cai, Lane A. Hemachandra
1988	A*	`conf`	Take a Walk, Grow a Tree (Preliminary Version) FOCS Sandeep N. Bhatt, Jin-Yi Cai
1988	J	`jnl`	The Boolean Hierarchy I: Structural Properties. SIAM J. Comput. Jin-Yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung
1987	J	`jnl`	Graph Minimal Uncolorability is D^P-Complete. SIAM J. Comput. Jin-Yi Cai, Gabriele E. Meyer
1987	A*	`conf`	On the Complexity of Graph Critical Uncolorability. ICALP Jin-Yi Cai, Gabriele E. Meyer
1987	—	`conf`	PSPACE survives three-bit bottlenecks. SCT Jin-Yi Cai, Merrick L. Furst
1987	A	`conf`	Probability One Separation of the Boolean Hierarchy. STACS Jin-Yi Cai
1986	—	`—`	On Some Most Probable Separations of Complexity Classes. Jin-Yi Cai
1986	—	`conf`	The Boolean Hierarchy: Hardware over NP. SCT Jin-Yi Cai, Lane A. Hemachandra
1986	—	`conf`	With Probability One, A Random Oracle Separates PSPACE from the Polynomial- Time Hierarchy. SCT Jin-Yi Cai
1986	A*	`conf`	With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy STOC Jin-Yi Cai