Jin-Yi Cai | Academic Influence

Jin-Yi Cai's AcademicInfluence.com Rankings

Jin-Yi Cai

Computer Science

#1636

World Rank

#1691

Historical Rank

Theoretical Computer Science

#70

World Rank

#70

Historical Rank

Database

#7378

World Rank

#7645

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Jin-Yi Cai's Degrees

PhD Computer Science Cornell University
Masters Computer Science Cornell University
Bachelors Computer Science Tsinghua University

Similar Degrees You Can Earn

Why Is Jin-Yi Cai Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Jin-Yi Cai is a Chinese American mathematician and computer scientist. He is a professor of computer science, and also the Steenbock Professor of Mathematical Sciences at the University of Wisconsin–Madison. His research is in theoretical computer science, especially computational complexity theory. In recent years he has concentrated on the classification of computational counting problems, especially counting graph homomorphisms, counting constraint satisfaction problems, and Holant problems as related to holographic algorithms.

(See a Problem?)

Jin-Yi Cai's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

An optimal lower bound on the number of variables for graph identification (1989) (541)
X-Diff: an effective change detection algorithm for XML documents (2003) (434)
The Boolean Hierarchy I: Structural Properties (1988) (203)
Circuit minimization problem (2000) (158)
The Boolean Hierarchy II: Applications (1989) (113)
On differentially private frequent itemset mining (2012) (111)
Graph Homomorphisms with Complex Values: A Dichotomy Theorem (2009) (108)
The cyclic coloring problem and estimation of spare hessian matrices (1986) (108)
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy (1986) (107)
An improved worst-case to average-case connection for lattice problems (1997) (106)
Holographic algorithms: from art to science (2007) (105)
Holographic Algorithms (2016) (94)
Holant problems and counting CSP (2009) (88)
Multiplicative equations over commuting matrices (1996) (81)
The Boolean Hierarchy: Hardware over NP (1986) (74)
A complete dichotomy rises from the capture of vanishing signatures: extended abstract (2012) (74)
On the Hardness of Permanent (1999) (70)
On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line (1994) (69)
Computational Complexity of Holant Problems (2011) (65)
Complexity of Counting CSP with Complex Weights (2011) (65)
Enumerative counting is hard (1988) (64)
Approximating the SVP to within a Factor (1+1/dimxi) Is NP-Hard under Randomized Reductions (1999) (63)
Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness (2008) (61)
Non-negatively Weighted #CSP: An Effective Complexity Dichotomy (2010) (60)
Towards uncheatable benchmarks (1993) (57)
The complexity of complex weighted Boolean #CSP (2014) (55)
From Holant to #CSP and Back: Dichotomy for Holantc Problems (2010) (54)
Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP (2010) (53)
PSPACE Survives Constant-Width Bottlenecks (1991) (53)
Pseudorandom generators, measure theory, and natural proofs (1995) (53)
Valiant's Holant Theorem and matchgate tensors (2006) (52)
On the Theory of Matchgate Computations (2007) (52)
Competing provers yield improved Karp-Lipton collapse results (2003) (51)
On Routing in Circulant Graphs (1999) (50)
#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region (2013) (49)
On the correlation of symmetric functions (1996) (48)
Approximation and hardness results for label cut and related problems (2011) (45)
PSPACE is provable by two provers in one round (1991) (44)
Take a walk, grow a tree (1988) (42)
Computing Jordan Normal Forms Exactly for Commuting Matrices in Polynomial Time (1994) (41)
Estimation of congestion price using probabilistic packet marking (2003) (41)
A Lattice-Based Public-Key Cryptosystem (1998) (41)
Some Results on Matchgates and Holographic Algorithms (2006) (40)
On the power of parity polynomial time (1989) (40)
Taking random walks to grow trees in hypercubes (1993) (40)
A Relation of Primal-Dual Lattices and the Complexity of Shortest Lattice Vector Problem (1998) (39)
On Symmetric Signatures in Holographic Algorithms (2007) (38)
Graph Minimal Uncolorability is D^P-Complete (1987) (35)
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights (2010) (35)
Holographic algorithms: The power of dimensionality resolved (2007) (34)
Lower bounds for constant depth circuits in the presence of help bits (1989) (32)
On bounded round multiprover interactive proof systems (1990) (31)
On the Existence of Hard Sparse Sets under Weak Reductions (1996) (30)
On A Scheduling Problem of Time Deteriorating Jobs (1998) (30)
Some recent progress on the complexity of lattice problems (1999) (29)
The Complexity of the A B C Problem (2000) (29)
A Holant Dichotomy: Is the FKT Algorithm Universal? (2015) (29)
Basis Collapse in Holographic Algorithms (2007) (28)
A computational proof of complexity of some restricted counting problems (2009) (26)
Probability One Separation of the Boolean Hierarchy (1987) (24)
Holographic algorithm with matchgates is universal for planar #CSP over boolean domain (2016) (24)
Holographic reduction, interpolation and hardness (2012) (23)
The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems (2014) (23)
S2p⊆ZPPNP (2007) (23)
S p 2 ⊆ ZPP NP (2007) (22)
An Attacker-Defender Game for Honeynets (2009) (22)
Promises and fault-tolerant database access (1993) (22)
Playing Games of Incomplete Information (1990) (22)
Dichotomy for Holant∗ Problems on the Boolean Domain (2011) (22)
The resolution of a Hartmanis conjecture (1995) (22)
Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic (2010) (21)
Matchgates Revisited (2013) (21)
The complexity of the membership problem for 2-generated commutative semigroups of rational matrices (1994) (20)
Approximating the Svp to within a Factor ? (2007) (20)
Holographic algorithms by Fibonacci gates (2013) (20)
Cache Placement Methods Based on Client Demand Clustering (2002) (20)
A Note on the Determinant and Permanent Problem (1990) (19)
Fine Separation of Average-Time Complexity Classes (1999) (19)
The minimum consistent subset cover problem and its applications in data mining (2007) (19)
A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor (2003) (19)
Holant Problems for 3-Regular Graphs with Complex Edge Functions (2010) (19)
Spin systems on k-regular graphs with complex edge functions (2012) (18)
On Tractable Exponential Sums (2010) (18)
Dichotomy for Real Holantc Problems (2018) (18)
Promise Problems and Access to Unambiguous Computation (1992) (18)
Constant depth circuits and the Lutz hypothesis (1997) (18)
Applications of a new transference theorem to Ajtai's connection factor (1999) (17)
The Complexity of Some Lattice Problems (2000) (17)
On Games of Incomplete Information (1992) (17)
Dichotomy for real holant c problems (2017) (17)
Subquadratic simulations of circuits by branching programs (1989) (16)
Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis (1999) (16)
Dichotomy for Holant* Problems with Domain Size 3 (2013) (16)
Camouflaging Honeynets (2007) (15)
Gadgets and anti-gadgets leading to a complexity dichotomy (2011) (15)
On the complexity of join predicates (2001) (15)
A quadratic lower bound for the permanent and determinant problem over any characteristic ≠ 2 (2008) (14)
PSPACE survives three-bit bottlenecks (1987) (14)
Resolution of Hartmanis' conjecture for NL-hard sparse sets (1997) (14)
Signature Theory in Holographic Algorithms (2008) (14)
On testing for zero polynomials by a set of points with bounded precision (2001) (14)
Complexity of counting CSP with complex weights (2012) (14)
Sparse sets versus complexity classes (1998) (14)
Reliable benchmarks using numerical instability (1994) (13)
A note on the non-NP-hardness of approximate lattice problems under general Cook reductions (2000) (13)
Advances In Computational Complexity Theory (1993) (13)
Approximating the SVP to within a factor (1-1/dim/sup /spl epsiv//) is NP-hard under randomized conditions (1998) (13)
Preface to Special Issue: Theory and Applications of Models of Computation (TAMC) (2009) (13)
On Some Most Probable Separations of Complexity Classes (1986) (12)
Parallel computation over hyperbolic groups (1992) (12)
Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms (2019) (12)
Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions (1998) (12)
Approximability of the Six-vertex Model (2017) (11)
A Note on Enumarative Counting (1991) (11)
A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions (2010) (11)
Dichotomy theorems for holant problems (2010) (11)
Honeynet games: a game theoretic approach to defending network monitors (2011) (11)
Hardness and hierarchy theorems for probabilistic quasi-polynomial time (1999) (11)
Efficient average-case algorithms for the modular group (1994) (10)
On the average-case hardness of CVP (2001) (10)
Time-Space Tradeoff in Derandomizing Probabilistic Logspace (2004) (10)
Making benchmarks uncheatable (1998) (10)
A Dichotomy for Real Boolean Holant Problems (2020) (9)
Exact Counting is as Easy as Approximate Counting (1986) (9)
Complexity classification of the six-vertex model (2017) (9)
Holographic Algorithms Beyond Matchgates (2013) (9)
Complexity Dichotomies for Counting Problems by Jin-Yi Cai (2017) (9)
Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs (2005) (9)
Inapproximability after Uniqueness Phase Transition in Two-Spin Systems (2012) (9)
Subquadratic Simulations of Balanced Formulae by Branching Programs (1994) (9)
Average Time Complexity Classes (1995) (9)
A new transference theorem and applications to Ajtai's connection factor (1998) (8)
Partition functions on kk-regular graphs with {0, 1}{0, 1}-vertex assignments and real edge functions (2013) (8)
Robust Reductions (1998) (8)
On a Theorem of Lovász that hom(·, H) Determines the Isomorhphism Type of H (2020) (8)
On zero error algorithms having oracle access to one query (2006) (8)
A collapse theorem for holographic algorithms with matchgates on domain size at most 4 (2013) (7)
Clifford Gates in the Holant Framework (2017) (7)
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy (2004) (7)
Complexity Classification of the Eight-Vertex Model (2017) (7)
Repair Tolerance Analysis for Composite Structures Using Probabilistic Methodologies (2014) (7)
Approximating the SVP to within a factor (1 + 1/dimepsilon) is NP-hard under randomized reductions (1997) (7)
Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic Geometry (1994) (6)
On blockwise symmetric signatures for matchgates (2007) (6)
FKT is Not Universal — A Planar Holant Dichotomy for Symmetric Constraints (2021) (6)
Approximability of the eight-vertex model (2018) (6)
A dichotomy for bounded degree graph homomorphisms with nonnegative weights (2020) (5)
Holographic algorithms with unsymmetric signatures (2008) (5)
Promise Problems and Guarded Access to Unambiguous Computation (1992) (5)
Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities (2011) (5)
Efficient Algorithms for a Scheduling Problem and its Applications to Illicit Drug Market Crackdowns (1998) (5)
A New Transference Theorem in the Geometry of Numbers (1999) (5)
Counting perfect matchings and the eight-vertex model (2019) (5)
Communication Complexity of Key Agreement on Small Ranges (1995) (5)
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results (2003) (5)
Design of Uncheatable Benchmarks Using Complexity Theory (1997) (5)
Holographic algorithms: guest column (2008) (4)
On the Complexity of Graph Critical Uncolorability (1987) (4)
Communication Complexity of Key Agreement on Limited Ranges (1994) (4)
From Holant to Quantum Entanglement and Back (2020) (4)
Computations Over Infinite Groups (1991) (4)
Fine Separation of Average Time Complexity Classes (1996) (4)
The bounded membership problem of the monoidSL2(N) (1996) (4)
The Minimum Consistent Subset Cover Problem: A Minimization View of Data Mining (2013) (4)
Essentially Every Unimodular Matrix Defines an Expander (2000) (3)
Bounded Truth Table Reductions of P (1995) (3)
Lectures in Computational Complexity (2003) (3)
A note on quadratic residuosity and UP (2004) (3)
Relativized collapsing between BPP and PH under stringent oracle access (2004) (3)
A Note on Zero Error Algorithms Having Oracle Access to One NP Query (2005) (2)
Bipartite 3-Regular Counting Problems with Mixed Signs (2021) (2)
S2p is subset of ZPPNP (2007) (2)
On optimal differentially private mechanisms for count-range queries (2013) (2)
Dichotomy for Holant* Problems with a Function on Domain Size 3 (2012) (2)
A Classification of the Probabilistic Polynomial Time Hierarchy Under Fault Tolerant Access to Oracle Classes (1999) (2)
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs (2020) (2)
Sp2 subseteq ZPPNP (2001) (2)
An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures (2021) (2)
Progress in Computational Complexity Theory (2005) (2)
Complexity of Counting Weighted Eulerian Orientations with ARS (2019) (2)
A Complexity Trichotomy for the Six-Vertex Model (2017) (2)
Random Access to Advice Strings and Collapsing Results (2004) (2)
On a Theorem of Lovász that $\hom(\cdot, H)$ Determines the Isomorhphism Type of $H$ (2019) (2)
On a Theorem of Lovász that (&sdot, H) Determines the Isomorphism Type of H (2021) (2)
FPRAS via MCMC where it mixes torpidly (and very little effort) (2020) (1)
S p ⊆ ZPP NP (2002) (1)
Holant Problems for 3-Regular Graphs with Complex Edge Functions (2016) (1)
On the 100% Rule of Sensivity Analzsis in Linear Programming (1997) (1)
New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification (2021) (1)
Complexity Dichotomy for Counting Problems (2017) (1)
Approximating the Partition Function of Two-Spin Systems on Bipartite Graphs (2013) (1)
Holant Problems (2016) (1)
Fully Polynomial Time Approximation Scheme in Scheduling Deteriorating Jobs (1994) (1)
Foreword: Foreword (2011) (1)
Average-case versus worst-case complexity of computation (1999) (1)
On Proving Circuit Lower Bounds Against PH and Some Related Lower Bounds for Constant Depth Circuits (2003) (1)
On the Impossibility of Amplifying the Independence of Random Variables (1995) (1)
Frobenius's Degree Formula and Toda's Polynomials (1998) (1)
Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy (2019) (1)
On Higher Arthur-Merlin Classes (2002) (1)
From Holant to #CSP and Back: Dichotomy for Holantc Problems (2012) (1)
Theory and Applications of Models of Computation: Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006, Proceedings (Lecture Notes in Computer Science) (2006) (1)
Estimation of Probabilistic Congestion Price Using Packet Marking (2003) (1)
The Complexity of Counting Edge Colorings for Simple Graphs (2020) (1)
On P-selective Sets and Adaptive versus Nonadaptive Queries to Np (1994) (1)
Approximation and Hardness Results for Label Cut and Related Problems (2009) (1)
Dichotomy Result on 3-Regular Bipartite Non-negative Functions (2020) (1)
Holant Dichotomy for Symmetric Constraints (2017) (0)
S p 2 (0)
S_2 p \subseteq ZPP NP (2001) (0)
Foreword (2011) (0)
Edinburgh Research Explorer Clifford Gates in the Holant Framework (2018) (0)
CS 880 : Complexity of Counting Problems 03 / 08 / 2012 Lecture 14 : (2012) (0)
Complexity Dichotomies for Counting Graph Homomorphisms (2016) (0)
Holant Problems and #CSP (2017) (0)
Self-stabilization by Tree Correction (info) Self-stabilization by Tree Correction (info) Self-stabilization by Tree Correction (1995) (0)
Properties of Position Matrices and Their Elections (2023) (0)
Session details: Session 6B (2005) (0)
Matchgates and Holographic Algorithms (2017) (0)
A Worst-Case to Average-Case Connection for CVP (2007) (0)
On the Minimum Volume of a Perturbed Unit Cube (2002) (0)
FKT is Not Universal — A Planar Holant Dichotomy for Symmetric Constraints (2021) (0)
Session details: Session 2A (2005) (0)
Take a Walk, Grow a Tree (Preliminary Version) (1988) (0)
A Family of Counter Examples to an Approach to Graph Isomorphism (2008) (0)
Holographic Algorithms on Domain Size k > 2 (2012) (0)
Relativized Collapsing Results under Stringent Oracle Access (2002) (0)
S_2p \subseteq ZPPNP (2001) (0)
LA-1 Relativized Collapsing Results under Stringent Oracle Access (2002) (0)
Dichotomies for Asymmetric Constraints (2017) (0)
Proceedings of the 4th international conference on Theory and applications of models of computation (2007) (0)
The complexity of counting planar graph homomorphisms of domain size 3 (2023) (0)
Two Remarks on Self-Correctability versus Random-Self-Reducibility (1994) (0)
Foundations of Software Technology and Theoretical Computer Science (1998) (0)
Planar #CSP for Symmetric Constraints (2017) (0)
Planar Holant for Symmetric Constraints (2017) (0)
Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint (2022) (0)
Computing and combinatorics : Second Annual International Conference, COCOON '96, Hong Kong, June 17-19, 1996 : proceedings (1996) (0)
Weakly Growing Context-sensitive Grammars Chicago Journal of Theoretical Computer Science (1996) (0)
Counting Cycles on Planar Graphs in Subexponential Time (2022) (0)
Pspace-hard Functions Checkable Debate Systems and Approximation Algorithms for Pspace (2007) (0)
Holographic Algorithms on Domains of General Size (2022) (0)
Planar 3-way Edge Perfect Matching Leads to A Holant Dichotomy (2023) (0)
Theory and Applications of Models of Computation, Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006, Proceedings (2006) (0)
Complexity of Counting Problems 04 / 10 / 2012 Lecture 21 : Claims 8 . 2-8 (2012) (0)
Lecture 8: Universal Algebra (2012) (0)
Complexity of Counting Problems 2 / 2 / 2012 Lecture 4 : Baby Dichotomy Theorem-Part 2 (2012) (0)
Progress in Complexity of Counting Problems (2011) (0)
Lecture 7: General Dichotomy (2012) (0)
Theory and Applications of Models of Computation, 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, Proceedings (2007) (0)
Erratum to: Signature Theory in Holographic Algorithms (2016) (0)
Holographic reduction, interpolation and hardness (2012) (0)
Computer and Information Sciences Fall 2013 Distinguished Lecture (2013) (0)
Erratum to: Signature Theory in Holographic Algorithms (2015) (0)
Stringent Relativization (2003) (0)
2-Spin Systems on Regular Graphs (2017) (0)
The Design of Uncheatable Benchmarks UsingComplexity Theory (1997) (0)
Interpolation and Hardness (2008) (0)
A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory (2018) (0)
Fibonacci Gates and Holant* Problems (2017) (0)
Multiplicative equations over commuting matrices (Extended Abstract) (1994) (0)
A Novel Information Transmission Problem and Its Optimal Solution (2007) (0)
Bounded Degree Nonnegative Counting CSP (2022) (0)
Lecture 4: Baby Dichotomy Theorem - Part 2 (2012) (0)
On the Impossibility of Certain Ranking Functions (2007) (0)
Complexity of Counting Problems 03 / 20 / 2012 Lecture 17 : Reduction to Discrete Unitary Matrix ( Step 2 . 1 ) (2012) (0)
Lecture 14: Probabilistic Computation, Max-cut (0)

This paper list is powered by the following services:

Other Resources About Jin-Yi Cai

en.wikipedia.org

What Schools Are Affiliated With Jin-Yi Cai?

Jin-Yi Cai is affiliated with the following schools: