| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Jin-Yi Cai, Heng Guo, Tyson Williams |
A Complete Dichotomy Rises from the Capture of Vanishing Signatures  |
CoRR  |
2012 |
DBLP BibTeX RDF |
|
| 1 | Zhiguo Fu, Jin-Yi Cai |
Holographic Algorithms on Domain Size k > 2. |
TAMC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Michael Kowalczyk, Tyson Williams |
Gadgets and anti-gadgets leading to a complexity dichotomy. |
ITCS |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-Yi Cai, Xi Chen |
Complexity of counting CSP with complex weights. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Peng Zhang, Jin-yi Cai, Linqing Tang, Wenbo Zhao |
Approximation and hardness results for label cut and related problems. |
J. Comb. Optim. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Vinod Yegneswaran, Chris Alfeld, Paul Barford |
Honeynet games: a game theoretic approach to defending network monitors. |
J. Comb. Optim. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu, Mingji Xia |
A computational proof of complexity of some restricted counting problems. |
Theor. Comput. Sci. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
Signature Theory in Holographic Algorithms. |
Algorithmica |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen |
Complexity of Counting CSP with Complex Weights |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Michael Kowalczyk, Tyson Williams |
Gadgets and Anti-gadgets Leading to a Complexity Dichotomy |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
Holographic algorithms: From art to science. |
J. Comput. Syst. Sci. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Alan L. Selman |
Foreword. |
J. Comput. Syst. Sci. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu, Mingji Xia |
Computational Complexity of Holant Problems. |
SIAM J. Comput. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu, Mingji Xia |
Dichotomy for Holant* Problems of Boolean Domain. |
SODA |
2011 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai |
Progress in Complexity of Counting Problems. |
FAW-AAIM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Michael Kowalczyk |
Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities. |
COCOON |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen, Pinyan Lu |
Non-negatively Weighted #CSP: An Effective Complexity Dichotomy. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
On blockwise symmetric signatures for matchgates. |
Theor. Comput. Sci. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen, Dong Li |
Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen, Pinyan Lu |
Non-negative Weighted #CSPs: An Effective Complexity Dichotomy |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Sangxia Huang, Pinyan Lu |
From Holant To #CSP And Back: Dichotomy For Holant$^c$ Problems |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Michael Kowalczyk, Jin-yi Cai |
Holant Problems for Regular Graphs with Complex Edge Functions |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu |
On Tractable Exponential Sums |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen |
A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu, Mingji Xia |
Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
On Symmetric Signatures in Holographic Algorithms. |
Theory Comput. Syst. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu |
On Tractable Exponential Sums. |
FAW |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen, Pinyan Lu |
Graph Homomorphisms with Complex Values: A Dichotomy Theorem. |
ICALP |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Michael Kowalczyk |
A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions. |
TAMC |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Kowalczyk, Jin-yi Cai |
Holant Problems for Regular Graphs with Complex Edge Functions. |
STACS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen |
A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu, Mingji Xia |
Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Sangxia Huang, Pinyan Lu |
From Holant to #CSP and Back: Dichotomy for Holantc Problems. |
ISAAC |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
Holographic algorithms: The power of dimensionality resolved. |
Theor. Comput. Sci. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, S. Barry Cooper, Angsheng Li |
Preface to Special Issue: Theory and Applications of Models of Computation (TAMC). |
Mathematical Structures in Computer Science |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen, Pinyan Lu |
Graph Homomorphisms with Complex Values: A Dichotomy Theorem |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Vinay Choudhary, Pinyan Lu |
On the Theory of Matchgate Computations. |
Theory Comput. Syst. |
2009 |
DBLP DOI BibTeX RDF |
Matchgates, Grassmann-Plücker identities, Holographic algorithms |
| 1 | Jin-yi Cai, Pinyan Lu, Mingji Xia |
A Computational Proof of Complexity of Some Restricted Counting Problems. |
TAMC |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Peng Zhang, Jin-yi Cai, Linqing Tang, Wenbo Zhao |
Approximation and Hardness Results for Label Cut and Related Problems. |
TAMC |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Vinod Yegneswaran, Chris Alfeld, Paul Barford |
An Attacker-Defender Game for Honeynets. |
COCOON |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu, Mingji Xia |
Holant problems and counting CSP. |
STOC |
2009 |
DBLP DOI BibTeX RDF |
holant problem, holographic reduction, CSP, polynomial interpolation |
| 1 | Jin-yi Cai, Pinyan Lu |
Basis Collapse in Holographic Algorithms. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
68Q25, Subject classification. 68Q17 |
| 1 | Jin-yi Cai, Pinyan Lu, Mingji Xia |
A Family of Counter Examples to an Approach to Graph Isomorphism |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai |
Holographic algorithms: guest column. |
SIGACT News |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
Holographic algorithms with unsymmetric signatures. |
SODA |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu, Mingji Xia |
Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
Signature Theory in Holographic Algorithms. |
ISAAC |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen, Dong Li |
A quadratic lower bound for the permanent and determinant problem over any characteristic != 2. |
STOC |
2008 |
DBLP DOI BibTeX RDF |
arithmetic complexity, finite field, determinant, permanent |
| 1 | Jin-yi Cai, Vinay Choudhary |
Some Results on Matchgates and Holographic Algorithms. |
Int. J. Software and Informatics |
2007 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
Holographic Algorithms: The Power of Dimensionality Resolved. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
Bases Collapse in Holographic Algorithms. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
On Block-wise Symmetric Signatures for Matchgates. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Vinay Choudhary |
Valiant's Holant Theorem and matchgate tensors. |
Theor. Comput. Sci. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai |
S2p is subset of ZPPNP. |
J. Comput. Syst. Sci. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
Holographic Algorithms: The Power of Dimensionality Resolved. |
ICALP |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, S. Barry Cooper, Hong Zhu (eds.) |
Theory and Applications of Models of Computation, 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, Proceedings |
TAMC |
2007 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
On Symmetric Signatures in Holographic Algorithms. |
STACS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Bach, Jin-yi Cai |
A Novel Information Transmission Problem and Its Optimal Solution. |
FCT |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
On Block-Wise Symmetric Signatures for Matchgates. |
FCT |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Vinay Choudhary, Pinyan Lu |
On the Theory of Matchgate Computations. |
IEEE Conference on Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
Bases Collapse in Holographic Algorithms. |
IEEE Conference on Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
Holographic algorithms: from art to science. |
STOC |
2007 |
DBLP DOI BibTeX RDF |
matchgates, signatures, holographic algorithms |
| 1 | Byron J. Gao, Martin Ester, Jin-yi Cai, Oliver Schulte, Hui Xiong |
The minimum consistent subset cover problem and its applications in data mining. |
KDD |
2007 |
DBLP DOI BibTeX RDF |
converse k-clustering, minimum consistent subset cover, minimum rule set, pattern summarization |
| 1 | Jin-yi Cai, Venkatesan T. Chakaravarthy |
On zero error algorithms having oracle access to one query. |
J. Comb. Optim. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Vinay Choudhary |
On the Theory of Matchgate Computations |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
On Symmetric Signatures in Holographic Algorithms. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
Holographic Algorithms: From Art to Science. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Vinay Choudhary |
Some Results on Matchgates and Holographic Algorithms. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Osamu Watanabe |
Random Access to Advice Strings and Collapsing Results. |
Algorithmica |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek |
Time-Space Tradeoff in Derandomizing Probabilistic Logspace. |
Theory Comput. Syst. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Vinay Choudhary |
Some Results on Matchgates and Holographic Algorithms. |
ICALP |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, S. Barry Cooper, Angsheng Li (eds.) |
Theory and Applications of Models of Computation, Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006, Proceedings |
TAMC |
2006 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Vinay Choudhary |
Valiant's Holant Theorem and Matchgate Tensors. |
TAMC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Vinay Choudhary |
Valiant's Holant Theorem and Matchgate Tensors |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara |
Competing provers yield improved Karp-Lipton collapse results. |
Inf. Comput. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Hong Zhu |
Progress in Computational Complexity Theory. |
J. Comput. Sci. Technol. |
2005 |
DBLP DOI BibTeX RDF |
computational complexity theory, PCP theorem, logspace complexity, Reingold's theorem, GAP problem, complexity of lattice problems, worst-case to average-case reductions, extractors, pseudorandomness, inapproximability, primality testing, theoretical computer science, holographic algorithms |
| 1 | Jin-yi Cai, Venkatesan T. Chakaravarthy |
A Note on Zero Error Algorithms Having Oracle Access to One NP Query. |
COCOON |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Pinyan Lu, Jialin Zhang, Chung Keung Poon, Jin-yi Cai |
Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs. |
ISAAC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Osamu Watanabe |
Relativized collapsing between BPP and PH under stringent oracle access. |
Inf. Process. Lett. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Robert A. Threlfall |
A note on quadratic residuosity and UP. |
Inf. Process. Lett. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Denis Charles, Aduri Pavan, Samik Sengupta |
On Higher Arthur-Merlin Classes. |
Int. J. Found. Comput. Sci. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Osamu Watanabe |
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy. |
SIAM J. Comput. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Zheng Huang, Lei Chen 0003, Jin-yi Cai, Deborah S. Gross, David R. Musicant, Raghu Ramakrishnan, James J. Schauer, Stephen J. Wright |
Mass Spectrum Labeling: Theory and Practice. |
ICDM |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek |
Time-Space Tradeoff in Derandomizing Probabilistic Logspace. |
STACS |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Osamu Watanabe |
Random Access to Advice Strings and Collapsing Results. |
ISAAC |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Eric Bach |
On testing for zero polynomials by a set of points with bounded precision. |
Theor. Comput. Sci. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai |
Essentially Every Unimodular Matrix Defines an Expander. |
Theory Comput. Syst. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai |
A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor. |
Discrete Applied Mathematics |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuan Wang, David J. DeWitt, Jin-yi Cai |
X-Diff: An Effective Change Detection Algorithm for XML Documents. |
ICDE |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara |
Competing Provers Yield Improved Karp-Lipton Collapse Results. |
STACS |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Micah Adler, Jin-yi Cai, Jonathan K. Shapiro, Donald F. Towsley |
Estimation of Congestion Price Using Probabilistic Packet Marking. |
INFOCOM |
2003 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Osamu Watanabe |
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results. |
COCOON |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Osamu Watanabe |
Stringent Relativization. |
FSTTCS |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Denis Charles, Aduri Pavan, Samik Sengupta |
On Higher Arthur-Merlin Classes. |
COCOON |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai |
On the Minimum Volume of a Perturbed Unit Cube. |
ISAAC |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai |
Essentially every unimodular matrix defines an expander |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai |
S_2p \subseteq ZPPNP |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Eric Bach |
On Testing for Zero Polynomials by a Set of Points with Bounded Precision. |
COCOON |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai |
Sp2 subseteq ZPPNP. |
FOCS |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai |
On the Average-Case Hardness of CVP. |
FOCS |
2001 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")