| Year |
Citation |
Score |
| 2021 |
Cai J, Govorov A. On a Theorem of Lovász that (&sdot,
H
) Determines the Isomorphism Type of
H Acm Transactions On Computation Theory. 13: 1-25. DOI: 10.1145/3448641 |
0.394 |
|
| 2020 |
Cai J, Fu Z, Shao S. Beyond #CSP: A dichotomy for counting weighted Eulerian orientations with ARS Information & Computation. 104589. DOI: 10.1016/J.Ic.2020.104589 |
0.38 |
|
| 2020 |
Cai J, Lu P, Xia M. Dichotomy for Holant ∗ Problems on the Boolean Domain Theory of Computing Systems \/ Mathematical Systems Theory. 1-30. DOI: 10.1007/S00224-020-09983-8 |
0.503 |
|
| 2019 |
Cai J, Kowalczyk M, Williams T. Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy Acm Transactions On Computation Theory. 11: 1-26. DOI: 10.1145/3305272 |
0.747 |
|
| 2019 |
Cai J, Chen X. A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights Computational Complexity. 28: 345-408. DOI: 10.1007/S00037-019-00184-5 |
0.525 |
|
| 2018 |
Cai J, Fu Z, Xia M. Complexity classification of the six-vertex model Information & Computation. 259: 130-141. DOI: 10.1016/J.Ic.2018.01.003 |
0.435 |
|
| 2018 |
Cai J, Guo H, Williams T. Holographic Algorithms Beyond Matchgates Information & Computation. 259: 102-129. DOI: 10.1016/J.Ic.2018.01.002 |
0.46 |
|
| 2017 |
Cai J, Chen X. Complexity of Counting CSP with Complex Weights Journal of the Acm. 64: 1-39. DOI: 10.1145/2822891 |
0.437 |
|
| 2017 |
Cai J, Lu P, Xia M. Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP Siam Journal On Computing. 46: 853-889. DOI: 10.1137/16M1073984 |
0.535 |
|
| 2016 |
Cai J, Guo H, Williams T. The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems Research in the Mathematical Sciences. 3: 18. DOI: 10.1186/S40687-016-0067-8 |
0.447 |
|
| 2016 |
Cai J, Guo H, Williams T. A Complete Dichotomy Rises from the Capture of Vanishing Signatures Siam Journal On Computing. 45: 1671-1728. DOI: 10.1137/15M1049798 |
0.387 |
|
| 2016 |
Cai J, Chen X, Lu P. Nonnegative Weighted #CSP: An Effective Complexity Dichotomy Siam Journal On Computing. 45: 2177-2198. DOI: 10.1137/15M1032314 |
0.452 |
|
| 2016 |
Kowalczyk M, Cai JY. Holant Problems for 3-Regular Graphs with Complex Edge Functions Theory of Computing Systems. 1-26. DOI: 10.1007/S00224-016-9671-7 |
0.761 |
|
| 2014 |
Cai JY, Galanis A, Goldberg LA, Guo H, Jerrum M, Štefankovič D, Vigoda E. #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region Journal of Computer and System Sciences. DOI: 10.1016/J.Jcss.2015.11.009 |
0.416 |
|
| 2014 |
Cai J, Lu P, Xia M. The complexity of complex weighted Boolean #CSP Journal of Computer and System Sciences. 80: 217-236. DOI: 10.1016/J.Jcss.2013.07.003 |
0.458 |
|
| 2014 |
Cai J, Fu Z. A collapse theorem for holographic algorithms with matchgates on domain size at most 4 Information & Computation. 239: 149-169. DOI: 10.1016/J.Ic.2014.10.002 |
0.366 |
|
| 2013 |
Cai J, Chen X, Lu P. Graph Homomorphisms with Complex Values: A Dichotomy Theorem Siam Journal On Computing. 42: 924-1029. DOI: 10.1137/110840194 |
0.539 |
|
| 2013 |
Gao BJ, Ester M, Xiong H, Cai JY, Schulte O. The minimum consistent subset cover problem: A minimization view of data mining Ieee Transactions On Knowledge and Data Engineering. 25: 690-703. DOI: 10.1109/Tkde.2011.260 |
0.313 |
|
| 2013 |
Cai JY, Kowalczyk M. Partition functions on k-regular graphs with {0, 1}-vertex assignments and real edge functions Theoretical Computer Science. 494: 63-74. DOI: 10.1016/J.Tcs.2012.12.043 |
0.761 |
|
| 2013 |
Cai J, Lu P, Xia M. Holographic algorithms by Fibonacci gates Linear Algebra and Its Applications. 438: 690-707. DOI: 10.1016/J.Laa.2011.02.032 |
0.465 |
|
| 2012 |
Cai JY, Kowalczyk M. Spin systems on k-regular graphs with complex edge functions Theoretical Computer Science. 461: 2-16. DOI: 10.1016/J.Tcs.2012.01.021 |
0.74 |
|
| 2012 |
Cai J, Huang S, Lu P. From Holant to #CSP and Back: Dichotomy for Holantc Problems Algorithmica. 64: 511-533. DOI: 10.1007/S00453-012-9626-6 |
0.486 |
|
| 2012 |
Cai J, Lu P, Xia M. Holographic reduction, interpolation and hardness Computational Complexity. 21: 573-604. DOI: 10.1007/S00037-012-0044-6 |
0.519 |
|
| 2011 |
Cai J, Lu P, Xia M. Computational Complexity of Holant Problems Siam Journal On Computing. 40: 1101-1132. DOI: 10.1137/100814585 |
0.467 |
|
| 2011 |
Cai J, Lu P, Xia M. A computational proof of complexity of some restricted counting problems Theoretical Computer Science. 412: 2468-2485. DOI: 10.1016/J.Tcs.2010.10.039 |
0.52 |
|
| 2011 |
Cai J, Lu P. Holographic algorithms: From art to science Journal of Computer and System Sciences. 77: 41-61. DOI: 10.1016/J.Jcss.2010.06.005 |
0.386 |
|
| 2011 |
Zhang P, Cai J, Tang L, Zhao W. Approximation and hardness results for label cut and related problems Journal of Combinatorial Optimization. 21: 192-208. DOI: 10.1007/S10878-009-9222-0 |
0.438 |
|
| 2011 |
Cai J, Lu P. Signature Theory in Holographic Algorithms Algorithmica. 61: 779-816. DOI: 10.1007/S00453-009-9383-3 |
0.345 |
|
| 2011 |
Cai JY, Kowalczyk M. Spin systems on graphs with complex edge functions and specified degree regularities Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6842: 146-157. DOI: 10.1007/978-3-642-22685-4_13 |
0.389 |
|
| 2010 |
Kowalczyk M, Cai JY. Holant problems for regular graphs with complex edge functions Leibniz International Proceedings in Informatics, Lipics. 5: 525-536. DOI: 10.4230/LIPIcs.STACS.2010.2482 |
0.464 |
|
| 2010 |
Cai J, Lu P. On Symmetric Signatures in Holographic Algorithms Theory of Computing Systems \/ Mathematical Systems Theory. 46: 398-415. DOI: 10.1007/S00224-009-9229-Z |
0.352 |
|
| 2010 |
Cai J, Chen X, Li D. Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic Computational Complexity. 19: 37-56. DOI: 10.1007/S00037-009-0284-2 |
0.35 |
|
| 2010 |
Cai JY, Kowalczyk M. A dichotomy for k-regular graphs with {0, 1}-vertex assignments and real edge functions Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6108: 328-339. DOI: 10.1007/978-3-642-13562-0_30 |
0.46 |
|
| 2009 |
Cai J, Lu P. Holographic algorithms: The power of dimensionality resolved Theoretical Computer Science. 410: 1618-1628. DOI: 10.1016/J.Tcs.2008.12.047 |
0.327 |
|
| 2009 |
Cai J, Choudhary V, Lu P. On the Theory of Matchgate Computations Theory of Computing Systems \/ Mathematical Systems Theory. 45: 108-132. DOI: 10.1007/S00224-007-9092-8 |
0.341 |
|
| 2008 |
Cai J, Lu P. Basis Collapse in Holographic Algorithms Computational Complexity. 17: 254-281. DOI: 10.1007/S00037-008-0249-X |
0.417 |
|
| 2007 |
Gao BJ, Ester M, Schulte O, Cai JY, Xiong H. The minimum consistent subset cover problem and its applications in data mining Proceedings of the Acm Sigkdd International Conference On Knowledge Discovery and Data Mining. 310-319. DOI: 10.1145/1281192.1281228 |
0.333 |
|
| 2007 |
Cai J. S2p⊆ZPPNP Journal of Computer and System Sciences. 73: 25-35. DOI: 10.1016/J.Jcss.2003.07.015 |
0.334 |
|
| 2006 |
Cai JY, Chakaravarthy VT. On zero error algorithms having oracle access to one query Journal of Combinatorial Optimization. 11: 189-202. DOI: 10.1007/S10878-006-7130-0 |
0.691 |
|
| 2006 |
Cai J, Watanabe O. Random Access to Advice Strings and Collapsing Results Algorithmica. 46: 43-57. DOI: 10.1007/S00453-006-0078-8 |
0.432 |
|
| 2005 |
Cai JY, Chakaravarthy VT, Hemaspaandra LA, Ogihara M. Competing provers yield improved Karp-Lipton collapse results Information and Computation. 198: 1-23. DOI: 10.1016/J.Ic.2005.01.002 |
0.681 |
|
| 2005 |
Cai J, Zhu H. Progress in computational complexity theory Journal of Computer Science and Technology. 20: 735-750. DOI: 10.1007/S11390-005-0735-4 |
0.475 |
|
| 2004 |
Cai J, Charles D, Pavan A, Sengupta S. On Higher Arthur-Merlin Classes International Journal of Foundations of Computer Science. 15: 3-19. DOI: 10.1142/S0129054104002273 |
0.353 |
|
| 2004 |
Cai J, Watanabe O. On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy Siam Journal On Computing. 33: 984-1009. DOI: 10.1137/S0097539703422716 |
0.38 |
|
| 2004 |
Cai J, Threlfall RA. A note on quadratic residuosity and UP Information Processing Letters. 92: 127-131. DOI: 10.1016/J.Ipl.2004.06.015 |
0.415 |
|
| 2004 |
Cai J, Watanabe O. Relativized collapsing between BPP and PH under stringent oracle access Information Processing Letters. 90: 147-154. DOI: 10.1016/J.Ipl.2004.02.004 |
0.391 |
|
| 2004 |
Cai JY, Chakaravarthy VT, Van Melkebeek D. Time-space tradeoff in derandomizing probabilistic logspace Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2996: 571-583. DOI: 10.1007/S00224-005-1264-9 |
0.648 |
|
| 2003 |
Cai J, Bach E. On testing for zero polynomials by a set of points with bounded precision Theoretical Computer Science. 296: 15-25. DOI: 10.1016/S0304-3975(02)00429-2 |
0.379 |
|
| 2001 |
Cai JY, Chakaravarthy VT, Kaushik R, Naughton JF. On the complexity of join predicates Proceedings of the Acm Sigact-Sigmod-Sigart Symposium On Principles of Database Systems. 207-214. |
0.623 |
|
| 2000 |
Cai J, Lipton RJ, Zalcstein Y. The Complexity of the A B C Problem Siam Journal On Computing. 29: 1878-1888. DOI: 10.1137/S0097539794276853 |
0.43 |
|
| 2000 |
Cai J, Sivakumar D. Resolution of Hartmanis' conjecture for NL-hard sparse sets Theoretical Computer Science. 240: 257-269. DOI: 10.1016/S0304-3975(99)00234-0 |
0.312 |
|
| 2000 |
Cai J, Nerurkar A. A note on the non-NP-hardness of approximate lattice problems under general Cook reductions Information Processing Letters. 76: 61-66. DOI: 10.1016/S0020-0190(00)00123-X |
0.382 |
|
| 1999 |
Cai J. A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes Information Processing Letters. 69: 167-174. DOI: 10.1016/S0020-0190(99)00011-3 |
0.327 |
|
| 1999 |
Cai J, Nerurkar A. Approximating the SVP to within a Factor (1+1/dimε) Is NP-Hard under Randomized Reductions Journal of Computer and System Sciences. 59: 221-239. DOI: 10.1006/Jcss.1999.1649 |
0.361 |
|
| 1999 |
Cai JY, Cusick TW. A lattice- based public-key cryptosystem Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1556: 219-233. DOI: 10.1006/Inco.1998.2762 |
0.405 |
|
| 1998 |
Cai P, Cai J, Naik AV. Efficient Algorithms for a Scheduling Problem and its Applications to Illicit Drug Market Crackdowns Journal of Combinatorial Optimization. 1: 367-376. DOI: 10.1023/A:1009738610804 |
0.34 |
|
| 1998 |
Cai J. A relation of primal-dual lattices and the complexity of shortest lattice vector problem Theoretical Computer Science. 207: 105-116. DOI: 10.1016/S0304-3975(98)00058-9 |
0.447 |
|
| 1996 |
Cai JY, Selman AL. Fine separation of average time complexity classes Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1046: 331-343. DOI: 10.1137/S0097539796311715 |
0.356 |
|
| 1996 |
Cai J, Liu Z. The Bounded Membership Problem of the Monoid SL_2(N) Theory of Computing Systems \/ Mathematical Systems Theory. 29: 573-587. DOI: 10.1007/Bf01301965 |
0.385 |
|
| 1996 |
Cai J, Green F, Thierauf T. On the correlation of symmetric functions Theory of Computing Systems \/ Mathematical Systems Theory. 29: 245-258. DOI: 10.1007/Bf01201278 |
0.326 |
|
| 1994 |
Cai J. Computing Jordan Normal Forms Exactly For Commuting Matrices In Polynomial Time International Journal of Foundations of Computer Science. 5: 293-302. DOI: 10.1142/S0129054194000165 |
0.342 |
|
| 1992 |
Cai JY, Fürer M, Immerman N. An optimal lower bound on the number of variables for graph identification Combinatorica. 12: 389-410. DOI: 10.1007/Bf01305232 |
0.437 |
|
| 1991 |
Cai J, Furst ML. Pspace Survives Constant-Width Bottlenecks International Journal of Foundations of Computer Science. 2: 67-76. DOI: 10.1142/S0129054191000054 |
0.305 |
|
| 1991 |
Cai J, Hemachandra LA. A note on enumerative counting Information Processing Letters. 38: 215-219. DOI: 10.1016/0020-0190(91)90103-O |
0.325 |
|
| 1990 |
Cai Jy. Lower bounds for constant-depth circuits in the presence of help bits Information Processing Letters. 36: 79-83. DOI: 10.1016/0020-0190(90)90101-3 |
0.351 |
|
| 1990 |
Cai J, Hemachandra LA. On the power of parity polynomial time Theory of Computing Systems \/ Mathematical Systems Theory. 23: 95-106. DOI: 10.1007/Bf02090768 |
0.386 |
|
| 1989 |
Cai J. Enumerative counting is hard Information & Computation. 82: 34-44. DOI: 10.1016/0890-5401(89)90063-1 |
0.387 |
|
| 1988 |
Cai J, Gundermann T, Hartmanis J, Hemachandra LA, Sewelson V, Wagner K, Wechsung G. The Boolean hierarchy I: structural properties Siam Journal On Computing. 17: 1232-1252. DOI: 10.1137/0217078 |
0.37 |
|
| 1987 |
Cai J, Meyer GE. Graph minimal uncolorability is D P -complete Siam Journal On Computing. 16: 259-277. DOI: 10.1137/0216022 |
0.408 |
|
| 1986 |
Coleman TF, Cai JY. The cyclic coloring problem and estimation of spare hessian matrices Siam Journal On Algebraic and Discrete Methods. 7: 221-235. DOI: 10.1137/0607026 |
0.305 |
|
| Show low-probability matches. |