default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Jin-Yi Cai
@article{DBLP:journals/algorithmica/CaiM24,
author = {Jin{-}Yi Cai and
Ashwin Maran},
title = {Counting Cycles on Planar Graphs in Subexponential Time},
journal = {Algorithmica},
volume = {86},
number = {2},
pages = {656--693},
year = {2024},
url = {https://doi.org/10.1007/s00453-023-01182-4},
doi = {10.1007/S00453-023-01182-4},
timestamp = {Thu, 01 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/CaiM24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2402-13868,
author = {Jin{-}Yi Cai and
Jacob Kruse and
Kenneth Mayer and
Daniel P. Szabo},
title = {A Uniformly Random Solution to Algorithmic Redistricting},
journal = {CoRR},
volume = {abs/2402.13868},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2402.13868},
doi = {10.48550/ARXIV.2402.13868},
eprinttype = {arXiv},
eprint = {2402.13868},
timestamp = {Fri, 22 Mar 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2402-13868.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/CaiFGK23,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Kurt Girstmair and
Michael Kowalczyk},
title = {A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using
Number Theory},
journal = {Comput. Complex.},
volume = {32},
number = {1},
pages = {4},
year = {2023},
url = {https://doi.org/10.1007/s00037-023-00237-w},
doi = {10.1007/S00037-023-00237-W},
timestamp = {Mon, 05 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/CaiFGK23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/CaiF23,
author = {Jin{-}Yi Cai and
Zhiguo Fu},
title = {Complexity classification of the eight-vertex model},
journal = {Inf. Comput.},
volume = {293},
pages = {105064},
year = {2023},
url = {https://doi.org/10.1016/j.ic.2023.105064},
doi = {10.1016/J.IC.2023.105064},
timestamp = {Sat, 05 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/iandc/CaiF23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/GovorovCD23,
author = {Artem Govorov and
Jin{-}Yi Cai and
Martin E. Dyer},
title = {A dichotomy for bounded degree graph homomorphisms with nonnegative
weights},
journal = {J. Comput. Syst. Sci.},
volume = {132},
pages = {1--15},
year = {2023},
url = {https://doi.org/10.1016/j.jcss.2022.09.002},
doi = {10.1016/J.JCSS.2022.09.002},
timestamp = {Mon, 12 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/GovorovCD23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/CaiFL23,
author = {Jin{-}Yi Cai and
Austen Z. Fan and
Yin Liu},
title = {Bipartite 3-regular counting problems with mixed signs},
journal = {J. Comput. Syst. Sci.},
volume = {135},
pages = {15--31},
year = {2023},
url = {https://doi.org/10.1016/j.jcss.2023.01.006},
doi = {10.1016/J.JCSS.2023.01.006},
timestamp = {Fri, 21 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jcss/CaiFL23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/FuC23,
author = {Zhiguo Fu and
Jin{-}Yi Cai},
title = {Holographic Algorithms on Domains of General Size},
journal = {Theory Comput. Syst.},
volume = {67},
number = {3},
pages = {417--436},
year = {2023},
url = {https://doi.org/10.1007/s00224-022-10088-7},
doi = {10.1007/S00224-022-10088-7},
timestamp = {Fri, 21 Jul 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/FuC23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/FanC23,
author = {Austen Z. Fan and
Jin{-}Yi Cai},
title = {Dichotomy result on 3-regular bipartite non-negative functions},
journal = {Theor. Comput. Sci.},
volume = {949},
pages = {113745},
year = {2023},
url = {https://doi.org/10.1016/j.tcs.2023.113745},
doi = {10.1016/J.TCS.2023.113745},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/FanC23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/aaai/BoehmerCFFJ0W23,
author = {Niclas Boehmer and
Jin{-}Yi Cai and
Piotr Faliszewski and
Austen Z. Fan and
Lukasz Janeczko and
Andrzej Kaczmarczyk and
Tomasz Was},
editor = {Brian Williams and
Yiling Chen and
Jennifer Neville},
title = {Properties of Position Matrices and Their Elections},
booktitle = {Thirty-Seventh {AAAI} Conference on Artificial Intelligence, {AAAI}
2023, Thirty-Fifth Conference on Innovative Applications of Artificial
Intelligence, {IAAI} 2023, Thirteenth Symposium on Educational Advances
in Artificial Intelligence, {EAAI} 2023, Washington, DC, USA, February
7-14, 2023},
pages = {5507--5514},
publisher = {{AAAI} Press},
year = {2023},
url = {https://doi.org/10.1609/aaai.v37i5.25684},
doi = {10.1609/AAAI.V37I5.25684},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/aaai/BoehmerCFFJ0W23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoa/LiuFC23,
author = {Yin Liu and
Austen Z. Fan and
Jin{-}Yi Cai},
editor = {Weili Wu and
Jianxiong Guo},
title = {Restricted Holant Dichotomy on Domains 3 and 4},
booktitle = {Combinatorial Optimization and Applications - 17th International Conference,
{COCOA} 2023, Hawaii, HI, USA, December 15-17, 2023, Proceedings,
Part {II}},
series = {Lecture Notes in Computer Science},
volume = {14462},
pages = {83--96},
publisher = {Springer},
year = {2023},
url = {https://doi.org/10.1007/978-3-031-49614-1\_5},
doi = {10.1007/978-3-031-49614-1\_5},
timestamp = {Thu, 04 Jan 2024 08:13:47 +0100},
biburl = {https://dblp.org/rec/conf/cocoa/LiuFC23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/CaiY23,
author = {Jin{-}Yi Cai and
Ben Young},
editor = {Kousha Etessami and
Uriel Feige and
Gabriele Puppis},
title = {Planar {\#}CSP Equality Corresponds to Quantum Isomorphism - {A} Holant
Viewpoint},
booktitle = {50th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2023, July 10-14, 2023, Paderborn, Germany},
series = {LIPIcs},
volume = {261},
pages = {33:1--33:17},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2023.33},
doi = {10.4230/LIPICS.ICALP.2023.33},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/CaiY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CaiM23,
author = {Jin{-}Yi Cai and
Ashwin Maran},
editor = {Barna Saha and
Rocco A. Servedio},
title = {The Complexity of Counting Planar Graph Homomorphisms of Domain Size
3},
booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
pages = {1285--1297},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246.3585173},
doi = {10.1145/3564246.3585173},
timestamp = {Mon, 22 May 2023 13:01:48 +0200},
biburl = {https://dblp.org/rec/conf/stoc/CaiM23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2302-08570,
author = {Jin{-}Yi Cai and
Ashwin Maran},
title = {The complexity of counting planar graph homomorphisms of domain size
3},
journal = {CoRR},
volume = {abs/2302.08570},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2302.08570},
doi = {10.48550/ARXIV.2302.08570},
eprinttype = {arXiv},
eprint = {2302.08570},
timestamp = {Thu, 23 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2302-08570.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2303-02538,
author = {Niclas Boehmer and
Jin{-}Yi Cai and
Piotr Faliszewski and
Austen Z. Fan and
Lukasz Janeczko and
Andrzej Kaczmarczyk and
Tomasz Was},
title = {Properties of Position Matrices and Their Elections},
journal = {CoRR},
volume = {abs/2303.02538},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2303.02538},
doi = {10.48550/ARXIV.2303.02538},
eprinttype = {arXiv},
eprint = {2303.02538},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2303-02538.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2303-16705,
author = {Jin{-}Yi Cai and
Austen Z. Fan},
title = {Planar 3-way Edge Perfect Matching Leads to {A} Holant Dichotomy},
journal = {CoRR},
volume = {abs/2303.16705},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2303.16705},
doi = {10.48550/ARXIV.2303.16705},
eprinttype = {arXiv},
eprint = {2303.16705},
timestamp = {Fri, 14 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2303-16705.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2306-10072,
author = {Jin{-}Yi Cai},
title = {Shor's Algorithm Does Not Factor Large Integers in the Presence of
Noise},
journal = {CoRR},
volume = {abs/2306.10072},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2306.10072},
doi = {10.48550/ARXIV.2306.10072},
eprinttype = {arXiv},
eprint = {2306.10072},
timestamp = {Fri, 23 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2306-10072.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2307-16078,
author = {Yin Liu and
Austen Z. Fan and
Jin{-}Yi Cai},
title = {Restricted Holant Dichotomy on Domains 3 and 4},
journal = {CoRR},
volume = {abs/2307.16078},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2307.16078},
doi = {10.48550/ARXIV.2307.16078},
eprinttype = {arXiv},
eprint = {2307.16078},
timestamp = {Wed, 02 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2307-16078.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cpc/CaiG22,
author = {Jin{-}Yi Cai and
Artem Govorov},
title = {Perfect matchings, rank of connection tensors and graph homomorphisms},
journal = {Comb. Probab. Comput.},
volume = {31},
number = {2},
pages = {268--303},
year = {2022},
url = {https://doi.org/10.1017/S0963548321000286},
doi = {10.1017/S0963548321000286},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cpc/CaiG22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/CaiFGW22,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Heng Guo and
Tyson Williams},
title = {{FKT} is Not Universal - {A} Planar Holant Dichotomy for Symmetric
Constraints},
journal = {Theory Comput. Syst.},
volume = {66},
number = {1},
pages = {143--308},
year = {2022},
url = {https://doi.org/10.1007/s00224-021-10032-1},
doi = {10.1007/S00224-021-10032-1},
timestamp = {Tue, 08 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/mst/CaiFGW22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiF22,
author = {Jin{-}Yi Cai and
Zhiguo Fu},
title = {Holographic Algorithm with Matchgates Is Universal for Planar {\textbackslash}{\#}CSP
over Boolean Domain},
journal = {{SIAM} J. Comput.},
volume = {51},
number = {2},
pages = {17--50},
year = {2022},
url = {https://doi.org/10.1137/17m1131672},
doi = {10.1137/17M1131672},
timestamp = {Mon, 27 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiF22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/CaiM22,
author = {Jin{-}Yi Cai and
Ashwin Maran},
editor = {Yong Zhang and
Dongjing Miao and
Rolf H. M{\"{o}}hring},
title = {Counting Cycles on Planar Graphs in Subexponential Time},
booktitle = {Computing and Combinatorics - 28th International Conference, {COCOON}
2022, Shenzhen, China, October 22-24, 2022, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {13595},
pages = {268--279},
publisher = {Springer},
year = {2022},
url = {https://doi.org/10.1007/978-3-031-22105-7\_24},
doi = {10.1007/978-3-031-22105-7\_24},
timestamp = {Mon, 09 Jan 2023 17:58:31 +0100},
biburl = {https://dblp.org/rec/conf/cocoon/CaiM22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/CaiS22,
author = {Jin{-}Yi Cai and
Daniel P. Szabo},
editor = {Stefan Szeider and
Robert Ganian and
Alexandra Silva},
title = {Bounded Degree Nonnegative Counting {CSP}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer
Science, {MFCS} 2022, August 22-26, 2022, Vienna, Austria},
series = {LIPIcs},
volume = {241},
pages = {27:1--27:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.MFCS.2022.27},
doi = {10.4230/LIPICS.MFCS.2022.27},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/CaiS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2208-09948,
author = {Jin{-}Yi Cai and
Ashwin Maran},
title = {Counting Cycles on Planar Graphs in Subexponential Time},
journal = {CoRR},
volume = {abs/2208.09948},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2208.09948},
doi = {10.48550/ARXIV.2208.09948},
eprinttype = {arXiv},
eprint = {2208.09948},
timestamp = {Mon, 29 Aug 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2208-09948.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2212-03335,
author = {Jin{-}Yi Cai and
Ben Young},
title = {Planar {\#}CSP Equality Corresponds to Quantum Isomorphism - {A} Holant
Viewpoint},
journal = {CoRR},
volume = {abs/2212.03335},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2212.03335},
doi = {10.48550/ARXIV.2212.03335},
eprinttype = {arXiv},
eprint = {2212.03335},
timestamp = {Mon, 02 Jan 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2212-03335.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/CaiG21,
author = {Jin{-}Yi Cai and
Artem Govorov},
title = {The complexity of counting edge colorings for simple graphs},
journal = {Theor. Comput. Sci.},
volume = {889},
pages = {14--24},
year = {2021},
url = {https://doi.org/10.1016/j.tcs.2021.07.033},
doi = {10.1016/J.TCS.2021.07.033},
timestamp = {Fri, 08 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/CaiG21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/CaiG21,
author = {Jin{-}yi Cai and
Artem Govorov},
title = {On a Theorem of Lov{\'{a}}sz that ({\&}sdot, \emph{H}) Determines
the Isomorphism Type of \emph{H}},
journal = {{ACM} Trans. Comput. Theory},
volume = {13},
number = {2},
pages = {11:1--11:25},
year = {2021},
url = {https://doi.org/10.1145/3448641},
doi = {10.1145/3448641},
timestamp = {Tue, 15 Jun 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/CaiG21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/FanC21,
author = {Austen Z. Fan and
Jin{-}Yi Cai},
editor = {Rahul Santhanam and
Daniil Musatov},
title = {Dichotomy Result on 3-Regular Bipartite Non-negative Functions},
booktitle = {Computer Science - Theory and Applications - 16th International Computer
Science Symposium in Russia, {CSR} 2021, Sochi, Russia, June 28 -
July 2, 2021, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {12730},
pages = {102--115},
publisher = {Springer},
year = {2021},
url = {https://doi.org/10.1007/978-3-030-79416-3\_6},
doi = {10.1007/978-3-030-79416-3\_6},
timestamp = {Tue, 13 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/csr/FanC21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fct/CaiFL21,
author = {Jin{-}Yi Cai and
Austen Z. Fan and
Yin Liu},
editor = {Evripidis Bampis and
Aris Pagourtzis},
title = {Bipartite 3-Regular Counting Problems with Mixed Signs},
booktitle = {Fundamentals of Computation Theory - 23rd International Symposium,
{FCT} 2021, Athens, Greece, September 12-15, 2021, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {12867},
pages = {135--148},
publisher = {Springer},
year = {2021},
url = {https://doi.org/10.1007/978-3-030-86593-1\_9},
doi = {10.1007/978-3-030-86593-1\_9},
timestamp = {Thu, 16 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/fct/CaiFL21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CaiL21,
author = {Jin{-}Yi Cai and
Tianyu Liu},
editor = {D{\'{a}}niel Marx},
title = {An {FPTAS} for the square lattice six-vertex and eight-vertex models
at low temperatures},
booktitle = {Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2021, Virtual Conference, January 10 - 13, 2021},
pages = {1520--1534},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976465.92},
doi = {10.1137/1.9781611976465.92},
timestamp = {Mon, 15 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/CaiL21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CaiFS21,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Shuai Shao},
editor = {D{\'{a}}niel Marx},
title = {New Planar P-time Computable Six-Vertex Models and a Complete Complexity
Classification},
booktitle = {Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2021, Virtual Conference, January 10 - 13, 2021},
pages = {1535--1547},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976465.93},
doi = {10.1137/1.9781611976465.93},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/CaiFS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2110-01173,
author = {Jin{-}Yi Cai and
Austen Z. Fan and
Yin Liu},
title = {Bipartite 3-Regular Counting Problems with Mixed Signs},
journal = {CoRR},
volume = {abs/2110.01173},
year = {2021},
url = {https://arxiv.org/abs/2110.01173},
eprinttype = {arXiv},
eprint = {2110.01173},
timestamp = {Fri, 08 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2110-01173.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/CaiFS20,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Shuai Shao},
title = {Beyond {\#}CSP: {A} dichotomy for counting weighted Eulerian orientations
with {ARS}},
journal = {Inf. Comput.},
volume = {275},
pages = {104589},
year = {2020},
url = {https://doi.org/10.1016/j.ic.2020.104589},
doi = {10.1016/J.IC.2020.104589},
timestamp = {Tue, 29 Dec 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/CaiFS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/CaiLX20,
author = {Jin{-}Yi Cai and
Pinyan Lu and
Mingji Xia},
title = {Dichotomy for Holant\({}^{\mbox{{\({_\ast}\)}}}\) Problems on the
Boolean Domain},
journal = {Theory Comput. Syst.},
volume = {64},
number = {8},
pages = {1362--1391},
year = {2020},
url = {https://doi.org/10.1007/s00224-020-09983-8},
doi = {10.1007/S00224-020-09983-8},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/CaiLX20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiLLY20,
author = {Jin{-}Yi Cai and
Tianyu Liu and
Pinyan Lu and
Jing Yu},
editor = {Shubhangi Saraf},
title = {Approximability of the Eight-Vertex Model},
booktitle = {35th Computational Complexity Conference, {CCC} 2020, July 28-31,
2020, Saarbr{\"{u}}cken, Germany (Virtual Conference)},
series = {LIPIcs},
volume = {169},
pages = {4:1--4:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.CCC.2020.4},
doi = {10.4230/LIPICS.CCC.2020.4},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/CaiLLY20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001C20,
author = {Shuai Shao and
Jin{-}Yi Cai},
editor = {Sandy Irani},
title = {A Dichotomy for Real Boolean Holant Problems},
booktitle = {61st {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2020, Durham, NC, USA, November 16-19, 2020},
pages = {1091--1102},
publisher = {{IEEE}},
year = {2020},
url = {https://doi.org/10.1109/FOCS46700.2020.00105},
doi = {10.1109/FOCS46700.2020.00105},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/0001C20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiG20,
author = {Jin{-}Yi Cai and
Artem Govorov},
editor = {Sandy Irani},
title = {Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree
Graphs},
booktitle = {61st {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2020, Durham, NC, USA, November 16-19, 2020},
pages = {1103--1111},
publisher = {{IEEE}},
year = {2020},
url = {https://doi.org/10.1109/FOCS46700.2020.00106},
doi = {10.1109/FOCS46700.2020.00106},
timestamp = {Mon, 25 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CaiG20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/CaiF020,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Shuai Shao},
editor = {Artur Czumaj and
Anuj Dawar and
Emanuela Merelli},
title = {From Holant to Quantum Entanglement and Back},
booktitle = {47th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2020, July 8-11, 2020, Saarbr{\"{u}}cken, Germany (Virtual
Conference)},
series = {LIPIcs},
volume = {168},
pages = {22:1--22:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2020.22},
doi = {10.4230/LIPICS.ICALP.2020.22},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/CaiF020.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/CaiL20,
author = {Jin{-}Yi Cai and
Tianyu Liu},
editor = {Artur Czumaj and
Anuj Dawar and
Emanuela Merelli},
title = {Counting Perfect Matchings and the Eight-Vertex Model},
booktitle = {47th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2020, July 8-11, 2020, Saarbr{\"{u}}cken, Germany (Virtual
Conference)},
series = {LIPIcs},
volume = {168},
pages = {23:1--23:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2020.23},
doi = {10.4230/LIPICS.ICALP.2020.23},
timestamp = {Mon, 15 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/CaiL20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/GovorovCD20,
author = {Artem Govorov and
Jin{-}Yi Cai and
Martin E. Dyer},
editor = {Artur Czumaj and
Anuj Dawar and
Emanuela Merelli},
title = {A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative
Weights},
booktitle = {47th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2020, July 8-11, 2020, Saarbr{\"{u}}cken, Germany (Virtual
Conference)},
series = {LIPIcs},
volume = {168},
pages = {66:1--66:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2020.66},
doi = {10.4230/LIPICS.ICALP.2020.66},
timestamp = {Thu, 06 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icalp/GovorovCD20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/CaiG20,
author = {Jin{-}Yi Cai and
Artem Govorov},
editor = {Thomas Vidick},
title = {On a Theorem of Lov{\'{a}}sz that hom({\(\cdot\)}, {H)} Determines
the Isomorphism Type of {H}},
booktitle = {11th Innovations in Theoretical Computer Science Conference, {ITCS}
2020, January 12-14, 2020, Seattle, Washington, {USA}},
series = {LIPIcs},
volume = {151},
pages = {17:1--17:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2020.17},
doi = {10.4230/LIPICS.ITCS.2020.17},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/innovations/CaiG20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2002-02021,
author = {Artem Govorov and
Jin{-}Yi Cai and
Martin E. Dyer},
title = {A dichotomy for bounded degree graph homomorphisms with nonnegative
weights},
journal = {CoRR},
volume = {abs/2002.02021},
year = {2020},
url = {https://arxiv.org/abs/2002.02021},
eprinttype = {arXiv},
eprint = {2002.02021},
timestamp = {Thu, 06 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2002-02021.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2004-05706,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Shuai Shao},
title = {From Holant to Quantum Entanglement and Back},
journal = {CoRR},
volume = {abs/2004.05706},
year = {2020},
url = {https://arxiv.org/abs/2004.05706},
eprinttype = {arXiv},
eprint = {2004.05706},
timestamp = {Tue, 30 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2004-05706.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2004-06620,
author = {Jin{-}Yi Cai and
Artem Govorov},
title = {Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree
Graphs},
journal = {CoRR},
volume = {abs/2004.06620},
year = {2020},
url = {https://arxiv.org/abs/2004.06620},
eprinttype = {arXiv},
eprint = {2004.06620},
timestamp = {Tue, 21 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2004-06620.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2005-07906,
author = {Shuai Shao and
Jin{-}Yi Cai},
title = {A Dichotomy for Real Boolean Holant Problems},
journal = {CoRR},
volume = {abs/2005.07906},
year = {2020},
url = {https://arxiv.org/abs/2005.07906},
eprinttype = {arXiv},
eprint = {2005.07906},
timestamp = {Sat, 23 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2005-07906.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2010-04910,
author = {Jin{-}Yi Cai and
Artem Govorov},
title = {The Complexity of Counting Edge Colorings for Simple Graphs},
journal = {CoRR},
volume = {abs/2010.04910},
year = {2020},
url = {https://arxiv.org/abs/2010.04910},
eprinttype = {arXiv},
eprint = {2010.04910},
timestamp = {Tue, 20 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2010-04910.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2010-05425,
author = {Jin{-}Yi Cai and
Tianyu Liu},
title = {{FPRAS} via {MCMC} where it mixes torpidly (and very little effort)},
journal = {CoRR},
volume = {abs/2010.05425},
year = {2020},
url = {https://arxiv.org/abs/2010.05425},
eprinttype = {arXiv},
eprint = {2010.05425},
timestamp = {Mon, 15 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2010-05425.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2011-09110,
author = {Austen Z. Fan and
Jin{-}Yi Cai},
title = {Dichotomy Result on 3-Regular Bipartite Non-negative Functions},
journal = {CoRR},
volume = {abs/2011.09110},
year = {2020},
url = {https://arxiv.org/abs/2011.09110},
eprinttype = {arXiv},
eprint = {2011.09110},
timestamp = {Wed, 25 Nov 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2011-09110.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/CaiC19,
author = {Jin{-}Yi Cai and
Xi Chen},
title = {A decidable dichotomy theorem on directed graph homomorphisms with
non-negative weights},
journal = {Comput. Complex.},
volume = {28},
number = {3},
pages = {345--408},
year = {2019},
url = {https://doi.org/10.1007/s00037-019-00184-5},
doi = {10.1007/S00037-019-00184-5},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/CaiC19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/CaiKW19,
author = {Jin{-}Yi Cai and
Michael Kowalczyk and
Tyson Williams},
title = {Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy},
journal = {{ACM} Trans. Comput. Theory},
volume = {11},
number = {2},
pages = {7:1--7:26},
year = {2019},
url = {https://doi.org/10.1145/3305272},
doi = {10.1145/3305272},
timestamp = {Mon, 08 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/CaiKW19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CaiG19,
author = {Jin{-}Yi Cai and
Artem Govorov},
editor = {Timothy M. Chan},
title = {Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms},
booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9,
2019},
pages = {476--495},
publisher = {{SIAM}},
year = {2019},
url = {https://doi.org/10.1137/1.9781611975482.30},
doi = {10.1137/1.9781611975482.30},
timestamp = {Thu, 15 Jul 2021 13:49:01 +0200},
biburl = {https://dblp.org/rec/conf/soda/CaiG19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CaiLL19,
author = {Jin{-}Yi Cai and
Tianyu Liu and
Pinyan Lu},
editor = {Timothy M. Chan},
title = {Approximability of the Six-vertex Model},
booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9,
2019},
pages = {2248--2261},
publisher = {{SIAM}},
year = {2019},
url = {https://doi.org/10.1137/1.9781611975482.136},
doi = {10.1137/1.9781611975482.136},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/CaiLL19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1904-02362,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Shuai Shao},
title = {Complexity of Counting Weighted Eulerian Orientations with {ARS}},
journal = {CoRR},
volume = {abs/1904.02362},
year = {2019},
url = {http://arxiv.org/abs/1904.02362},
eprinttype = {arXiv},
eprint = {1904.02362},
timestamp = {Tue, 30 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1904-02362.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1904-10493,
author = {Jin{-}Yi Cai and
Tianyu Liu},
title = {Counting perfect matchings and the eight-vertex model},
journal = {CoRR},
volume = {abs/1904.10493},
year = {2019},
url = {http://arxiv.org/abs/1904.10493},
eprinttype = {arXiv},
eprint = {1904.10493},
timestamp = {Mon, 15 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1904-10493.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1909-03179,
author = {Jin{-}Yi Cai and
Artem Govorov},
title = {Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms},
journal = {CoRR},
volume = {abs/1909.03179},
year = {2019},
url = {http://arxiv.org/abs/1909.03179},
eprinttype = {arXiv},
eprint = {1909.03179},
timestamp = {Tue, 17 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1909-03179.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1909-03693,
author = {Jin{-}Yi Cai and
Artem Govorov},
title = {On a Theorem of Lov{\'{a}}sz that hom({\(\cdot\)}, {H)} Determines
the Isomorhphism Type of {H}},
journal = {CoRR},
volume = {abs/1909.03693},
year = {2019},
url = {http://arxiv.org/abs/1909.03693},
eprinttype = {arXiv},
eprint = {1909.03693},
timestamp = {Tue, 17 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1909-03693.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/CaiGW18,
author = {Jin{-}Yi Cai and
Heng Guo and
Tyson Williams},
title = {Holographic algorithms beyond matchgates},
journal = {Inf. Comput.},
volume = {259},
number = {1},
pages = {102--129},
year = {2018},
url = {https://doi.org/10.1016/j.ic.2018.01.002},
doi = {10.1016/J.IC.2018.01.002},
timestamp = {Wed, 04 Apr 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/iandc/CaiGW18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/CaiFX18,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Mingji Xia},
title = {Complexity classification of the six-vertex model},
journal = {Inf. Comput.},
volume = {259},
number = {Part},
pages = {130--141},
year = {2018},
url = {https://doi.org/10.1016/j.ic.2018.01.003},
doi = {10.1016/J.IC.2018.01.003},
timestamp = {Tue, 20 Mar 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/CaiFX18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/Cai0W18,
author = {Jin{-}Yi Cai and
Heng Guo and
Tyson Williams},
title = {Clifford gates in the Holant framework},
journal = {Theor. Comput. Sci.},
volume = {745},
pages = {163--171},
year = {2018},
url = {https://doi.org/10.1016/j.tcs.2018.06.010},
doi = {10.1016/J.TCS.2018.06.010},
timestamp = {Thu, 13 Sep 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/Cai0W18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/CaiFGK18,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Kurt Girstmair and
Michael Kowalczyk},
editor = {Anna R. Karlin},
title = {A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using
Number Theory},
booktitle = {9th Innovations in Theoretical Computer Science Conference, {ITCS}
2018, January 11-14, 2018, Cambridge, MA, {USA}},
series = {LIPIcs},
volume = {94},
pages = {2:1--2:22},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2018.2},
doi = {10.4230/LIPICS.ITCS.2018.2},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/innovations/CaiFGK18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CaiLX18,
author = {Jin{-}Yi Cai and
Pinyan Lu and
Mingji Xia},
editor = {Artur Czumaj},
title = {Dichotomy for Real Holant\({}^{\mbox{\emph{c}}}\) Problems},
booktitle = {Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018},
pages = {1802--1821},
publisher = {{SIAM}},
year = {2018},
url = {https://doi.org/10.1137/1.9781611975031.118},
doi = {10.1137/1.9781611975031.118},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/CaiLX18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1811-03126,
author = {Jin{-}Yi Cai and
Tianyu Liu and
Pinyan Lu and
Jing Yu},
title = {Approximability of the Eight-vertex Model},
journal = {CoRR},
volume = {abs/1811.03126},
year = {2018},
url = {http://arxiv.org/abs/1811.03126},
eprinttype = {arXiv},
eprint = {1811.03126},
timestamp = {Mon, 15 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1811-03126.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/CaiC17,
author = {Jin{-}Yi Cai and
Xi Chen},
title = {Complexity of Counting {CSP} with Complex Weights},
journal = {J. {ACM}},
volume = {64},
number = {3},
pages = {19:1--19:39},
year = {2017},
url = {https://doi.org/10.1145/2822891},
doi = {10.1145/2822891},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/CaiC17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiLX17,
author = {Jin{-}Yi Cai and
Pinyan Lu and
Mingji Xia},
title = {Holographic Algorithms with Matchgates Capture Precisely Tractable
Planar {\#}CSP},
journal = {{SIAM} J. Comput.},
volume = {46},
number = {3},
pages = {853--889},
year = {2017},
url = {https://doi.org/10.1137/16M1073984},
doi = {10.1137/16M1073984},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiLX17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CaiF17,
author = {Jin{-}Yi Cai and
Zhiguo Fu},
editor = {Hamed Hatami and
Pierre McKenzie and
Valerie King},
title = {Holographic algorithm with matchgates is universal for planar {\#}CSP
over boolean domain},
booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
pages = {842--855},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3055399.3055405},
doi = {10.1145/3055399.3055405},
timestamp = {Sun, 02 Jun 2019 21:10:31 +0200},
biburl = {https://dblp.org/rec/conf/stoc/CaiF17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/CaiLX17,
author = {Jin{-}Yi Cai and
Pinyan Lu and
Mingji Xia},
title = {Dichotomy for Real Holant\({}^{\mbox{c}}\) Problems},
journal = {CoRR},
volume = {abs/1702.02693},
year = {2017},
url = {http://arxiv.org/abs/1702.02693},
eprinttype = {arXiv},
eprint = {1702.02693},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/CaiLX17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/CaiFX17,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Mingji Xia},
title = {Complexity Classification Of The Six-Vertex Model},
journal = {CoRR},
volume = {abs/1702.02863},
year = {2017},
url = {http://arxiv.org/abs/1702.02863},
eprinttype = {arXiv},
eprint = {1702.02863},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/CaiFX17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/CaiF17,
author = {Jin{-}Yi Cai and
Zhiguo Fu},
title = {Complexity Classification of the Eight-Vertex Model},
journal = {CoRR},
volume = {abs/1702.07938},
year = {2017},
url = {http://arxiv.org/abs/1702.07938},
eprinttype = {arXiv},
eprint = {1702.07938},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/CaiF17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/CaiFS17,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Shuai Shao},
title = {A Complexity Trichotomy for the Six-Vertex Model},
journal = {CoRR},
volume = {abs/1704.01657},
year = {2017},
url = {http://arxiv.org/abs/1704.01657},
eprinttype = {arXiv},
eprint = {1704.01657},
timestamp = {Tue, 30 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/CaiFS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/CaiGW17,
author = {Jin{-}Yi Cai and
Heng Guo and
Tyson Williams},
title = {Clifford Gates in the Holant Framework},
journal = {CoRR},
volume = {abs/1705.00942},
year = {2017},
url = {http://arxiv.org/abs/1705.00942},
eprinttype = {arXiv},
eprint = {1705.00942},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/CaiGW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1712-05880,
author = {Jin{-}Yi Cai and
Tianyu Liu and
Pinyan Lu},
title = {Approximability of the Six-vertex Model},
journal = {CoRR},
volume = {abs/1712.05880},
year = {2017},
url = {http://arxiv.org/abs/1712.05880},
eprinttype = {arXiv},
eprint = {1712.05880},
timestamp = {Mon, 15 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1712-05880.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/CaiL16,
author = {Jin{-}Yi Cai and
Pinyan Lu},
title = {Erratum to: Signature Theory in Holographic Algorithms},
journal = {Algorithmica},
volume = {74},
number = {4},
pages = {1473--1476},
year = {2016},
url = {https://doi.org/10.1007/s00453-015-0090-y},
doi = {10.1007/S00453-015-0090-Y},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/CaiL16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/CaiGGGJSV16,
author = {Jin{-}Yi Cai and
Andreas Galanis and
Leslie Ann Goldberg and
Heng Guo and
Mark Jerrum and
Daniel Stefankovic and
Eric Vigoda},
title = {{\#}BIS-hardness for 2-spin systems on bipartite bounded degree graphs
in the tree non-uniqueness region},
journal = {J. Comput. Syst. Sci.},
volume = {82},
number = {5},
pages = {690--711},
year = {2016},
url = {https://doi.org/10.1016/j.jcss.2015.11.009},
doi = {10.1016/J.JCSS.2015.11.009},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/CaiGGGJSV16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/KowalczykC16,
author = {Michael Kowalczyk and
Jin{-}Yi Cai},
title = {Holant Problems for 3-Regular Graphs with Complex Edge Functions},
journal = {Theory Comput. Syst.},
volume = {59},
number = {1},
pages = {133--158},
year = {2016},
url = {https://doi.org/10.1007/s00224-016-9671-7},
doi = {10.1007/S00224-016-9671-7},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/KowalczykC16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiGW16,
author = {Jin{-}Yi Cai and
Heng Guo and
Tyson Williams},
title = {A Complete Dichotomy Rises from the Capture of Vanishing Signatures},
journal = {{SIAM} J. Comput.},
volume = {45},
number = {5},
pages = {1671--1728},
year = {2016},
url = {https://doi.org/10.1137/15M1049798},
doi = {10.1137/15M1049798},
timestamp = {Fri, 11 Aug 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiGW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiCL16,
author = {Jin{-}Yi Cai and
Xi Chen and
Pinyan Lu},
title = {Nonnegative Weighted {\#}CSP: An Effective Complexity Dichotomy},
journal = {{SIAM} J. Comput.},
volume = {45},
number = {6},
pages = {2177--2198},
year = {2016},
url = {https://doi.org/10.1137/15M1032314},
doi = {10.1137/15M1032314},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiCL16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/CaiCL16,
author = {Jin{-}Yi Cai and
Xi Chen and
Pinyan Lu},
title = {Complexity Dichotomies for Counting Graph Homomorphisms},
booktitle = {Encyclopedia of Algorithms},
pages = {366--369},
year = {2016},
url = {https://doi.org/10.1007/978-1-4939-2864-4\_747},
doi = {10.1007/978-1-4939-2864-4\_747},
timestamp = {Wed, 12 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/CaiCL16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/CaiGW16,
author = {Jin{-}Yi Cai and
Heng Guo and
Tyson Williams},
title = {Holant Problems},
booktitle = {Encyclopedia of Algorithms},
pages = {918--921},
year = {2016},
url = {https://doi.org/10.1007/978-1-4939-2864-4\_748},
doi = {10.1007/978-1-4939-2864-4\_748},
timestamp = {Fri, 11 Aug 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/CaiGW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/CaiLX16,
author = {Jin{-}Yi Cai and
Pinyan Lu and
Mingji Xia},
title = {Holographic Algorithms},
booktitle = {Encyclopedia of Algorithms},
pages = {921--926},
year = {2016},
url = {https://doi.org/10.1007/978-1-4939-2864-4\_746},
doi = {10.1007/978-1-4939-2864-4\_746},
timestamp = {Wed, 12 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/CaiLX16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/CaiF16,
author = {Jin{-}Yi Cai and
Zhiguo Fu},
title = {Holographic Algorithm with Matchgates Is Universal for Planar {\textdollar}{\textbackslash}{\#}{\textdollar}CSP
Over Boolean Domain},
journal = {CoRR},
volume = {abs/1603.07046},
year = {2016},
url = {http://arxiv.org/abs/1603.07046},
eprinttype = {arXiv},
eprint = {1603.07046},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/CaiF16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiFGW15,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Heng Guo and
Tyson Williams},
editor = {Venkatesan Guruswami},
title = {A Holant Dichotomy: Is the {FKT} Algorithm Universal?},
booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
2015, Berkeley, CA, USA, 17-20 October, 2015},
pages = {1259--1276},
publisher = {{IEEE} Computer Society},
year = {2015},
url = {https://doi.org/10.1109/FOCS.2015.81},
doi = {10.1109/FOCS.2015.81},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CaiFGW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/CaiFGW15,
author = {Jin{-}Yi Cai and
Zhiguo Fu and
Heng Guo and
Tyson Williams},
title = {A Holant Dichotomy: Is the {FKT} Algorithm Universal?},
journal = {CoRR},
volume = {abs/1505.02993},
year = {2015},
url = {http://arxiv.org/abs/1505.02993},
eprinttype = {arXiv},
eprint = {1505.02993},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/CaiFGW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/CaiF14,
author = {Jin{-}Yi Cai and
Zhiguo Fu},
title = {A collapse theorem for holographic algorithms with matchgates on domain
size at most 4},
journal = {Inf. Comput.},
volume = {239},
pages = {149--169},
year = {2014},
url = {https://doi.org/10.1016/j.ic.2014.10.002},
doi = {10.1016/J.IC.2014.10.002},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/CaiF14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/CaiLX14,
author = {Jin{-}Yi Cai and
Pinyan Lu and
Mingji Xia},
title = {The complexity of complex weighted Boolean {\#}CSP},
journal = {J. Comput. Syst. Sci.},
volume = {80},
number = {1},
pages = {217--236},
year = {2014},
url = {https://doi.org/10.1016/j.jcss.2013.07.003},
doi = {10.1016/J.JCSS.2013.07.003},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jcss/CaiLX14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/CaiG14,
author = {Jin{-}Yi Cai and
Aaron Gorenstein},
title = {Matchgates Revisited},
journal = {Theory Comput.},
volume = {10},
pages = {167--197},
year = {2014},
url = {https://doi.org/10.4086/toc.2014.v010a007},
doi = {10.4086/TOC.2014.V010A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/CaiG14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/CaiGGGJSV14,
author = {Jin{-}Yi Cai and
Andreas Galanis and
Leslie Ann Goldberg and
Heng Guo and
Mark Jerrum and
Daniel Stefankovic and
Eric Vigoda},
editor = {Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Nikhil R. Devanur and
Cristopher Moore},
title = {{\#}BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs
in the Tree Non-uniqueness Region},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2014, September 4-6, 2014, Barcelona,
Spain},
series = {LIPIcs},
volume = {28},
pages = {582--595},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2014},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.582},
doi = {10.4230/LIPICS.APPROX-RANDOM.2014.582},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/CaiGGGJSV14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiGW14,
author = {Jin{-}Yi Cai and
Heng Guo and
Tyson Williams},
title = {The Complexity of Counting Edge Colorings and a Dichotomy for Some
Higher Domain Holant Problems},
booktitle = {55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2014, Philadelphia, PA, USA, October 18-21, 2014},
pages = {601--610},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/FOCS.2014.70},
doi = {10.1109/FOCS.2014.70},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CaiGW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/CaiGW14,
author = {Jin{-}Yi Cai and
Heng Guo and
Tyson Williams},
editor = {Javier Esparza and
Pierre Fraigniaud and
Thore Husfeldt and
Elias Koutsoupias},
title = {Holographic Algorithms Beyond Matchgates},
booktitle = {Automata, Languages, and Programming - 41st International Colloquium,
{ICALP} 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {8572},
pages = {271--282},
publisher = {Springer},
year = {2014},
url = {https://doi.org/10.1007/978-3-662-43948-7\_23},
doi = {10.1007/978-3-662-43948-7\_23},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/CaiGW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/CaiGW14,
author = {Jin{-}Yi Cai and
Heng Guo and
Tyson Williams},
title = {The Complexity of Counting Edge Colorings and a Dichotomy for Some
Higher Domain Holant Problems},
journal = {CoRR},
volume = {abs/1404.4020},
year = {2014},
url = {http://arxiv.org/abs/1404.4020},
eprinttype = {arXiv},
eprint = {1404.4020},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/CaiGW14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiCL13,
author = {Jin{-}Yi Cai and
Xi Chen and
Pinyan Lu},
title = {Graph Homomorphisms with Complex Values: {A} Dichotomy Theorem},
journal = {{SIAM} J. Comput.},
volume = {42},
number = {3},
pages = {924--1029},
year = {2013},
url = {https://doi.org/10.1137/110840194},
doi = {10.1137/110840194},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiCL13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/CaiK13,
author = {Jin{-}Yi Cai and
Michael Kowalczyk},
title = {Partition functions on \emph{k}k-regular graphs with \{0, 1\}\{0,
1\}-vertex assignments and real edge functions},
journal = {Theor. Comput. Sci.},
volume = {494},
pages = {63--74},
year = {2013},
url = {https://doi.org/10.1016/j.tcs.2012.12.043},
doi = {10.1016/J.TCS.2012.12.043},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/CaiK13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tkde/GaoEXCS13,
author = {Byron J. Gao and
Martin Ester and
Hui Xiong and
Jin{-}Yi Cai and
Oliver Schulte},
title = {The Minimum Consistent Subset Cover Problem: {A} Minimization View
of Data Mining},
journal = {{IEEE} Trans. Knowl. Data Eng.},
volume = {25},
number = {3},
pages = {690--703},
year = {2013},
url = {https://doi.org/10.1109/TKDE.2011.260},
doi = {10.1109/TKDE.2011.260},
timestamp = {Fri, 03 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tkde/GaoEXCS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icdt/ZengCLN13,
author = {Chen Zeng and
Jin{-}Yi Cai and
Pinyan Lu and
Jeffrey F. Naughton},
editor = {Wang{-}Chiew Tan and
Giovanna Guerrini and
Barbara Catania and
Anastasios Gounaris},
title = {On optimal differentially private mechanisms for count-range queries},
booktitle = {Joint 2013 {EDBT/ICDT} Conferences, {ICDT} '13 Proceedings, Genoa,
Italy, March 18-22, 2013},
pages = {261--271},
publisher = {{ACM}},
year = {2013},
url = {https://doi.org/10.1145/2448496.2448528},
doi = {10.1145/2448496.2448528},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icdt/ZengCLN13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/lata/Cai13,
author = {Jin{-}Yi Cai},
editor = {Adrian{-}Horia Dediu and
Carlos Mart{\'{\i}}n{-}Vide and
Bianca Truthe},
title = {Complexity Dichotomy for Counting Problems},
booktitle = {Language and Automata Theory and Applications - 7th International
Conference, {LATA} 2013, Bilbao, Spain, April 2-5, 2013. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7810},
pages = {1--11},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-37064-9\_1},
doi = {10.1007/978-3-642-37064-9\_1},
timestamp = {Mon, 16 Sep 2019 15:27:03 +0200},
biburl = {https://dblp.org/rec/conf/lata/Cai13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CaiLX13,
author = {Jin{-}Yi Cai and
Pinyan Lu and
Mingji Xia},
editor = {Sanjeev Khanna},
title = {Dichotomy for Holant* Problems with Domain Size 3},
booktitle = {Proceedings of the Twenty-Fourth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2013, New Orleans, Louisiana, USA, January 6-8,
2013},
pages = {1278--1295},
publisher = {{SIAM}},
year = {2013},
url = {https://doi.org/10.1137/1.9781611973105.93},
doi = {10.1137/1.9781611973105.93},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/CaiLX13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CaiGW13,
author = {Jin{-}Yi Cai and
Heng Guo and
Tyson Williams},
editor = {Dan Boneh and
Tim Roughgarden and
Joan Feigenbaum},
title = {A complete dichotomy rises from the capture of vanishing signatures:
extended abstract},
booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA,
USA, June 1-4, 2013},
pages = {635--644},
publisher = {{ACM}},
year = {2013},
url = {https://doi.org/10.1145/2488608.2488687},
doi = {10.1145/2488608.2488687},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CaiGW13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1303-6729,
author = {Jin{-}Yi Cai and
Aaron Gorenstein},
title = {Matchgates Revisited},
journal = {CoRR},
volume = {abs/1303.6729},
year = {2013},
url = {http://arxiv.org/abs/1303.6729},
eprinttype = {arXiv},
eprint = {1303.6729},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1303-6729.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1305-1409,
author = {Jin{-}Yi Cai and
Zhiguo Fu},
title = {A Collapse Theorem for Holographic Algorithms with Matchgates on Domain
Size at Most 4},
journal = {CoRR},
volume = {abs/1305.1409},
year = {2013},
url = {http://arxiv.org/abs/1305.1409},
eprinttype = {arXiv},
eprint = {1305.1409},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1305-1409.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/CaiGW13,
author = {Jin{-}Yi Cai and
Heng Guo and
Tyson Williams},
title = {Holographic Algorithms Beyond Matchgates},
journal = {CoRR},
volume = {abs/1307.7430},
year = {2013},
url = {http://arxiv.org/abs/1307.7430},
eprinttype = {arXiv},
eprint = {1307.7430},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/CaiGW13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/CaiGGJ13,
author = {Jin{-}Yi Cai and
Leslie Ann Goldberg and
Heng Guo and
Mark Jerrum},
title = {Approximating the Partition Function of Two-Spin Systems on Bipartite
Graphs},
journal = {CoRR},
volume = {abs/1311.4451},
year = {2013},
url = {http://arxiv.org/abs/1311.4451},
eprinttype = {arXiv},
eprint = {1311.4451},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/CaiGGJ13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CaiG13,
author = {Jin{-}Yi Cai and
Aaron Gorenstein},
title = {Matchgates Revisited},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-048}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/048},
eprinttype = {ECCC},
eprint = {TR13-048},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CaiG13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/CaiHL12,
author = {Jin{-}Yi Cai and
Sangxia Huang and
Pinyan Lu},
title = {From Holant to {\#}CSP and Back: Dichotomy for Holant c Problems},
journal = {Algorithmica},
volume = {64},
number = {3},
pages = {511--533},
year = {2012},
url = {https://doi.org/10.1007/s00453-012-9626-6},
doi = {10.1007/S00453-012-9626-6},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/CaiHL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/CaiLX12,
author = {Jin{-}Yi Cai and
Pinyan Lu and
Mingji Xia},
title = {Holographic reduction, interpolation and hardness},
journal = {Comput. Complex.},
volume = {21},
number = {4},
pages = {573--604},
year = {2012},
url = {https://doi.org/10.1007/s00037-012-0044-6},
doi = {10.1007/S00037-012-0044-6},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/CaiLX12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/pvldb/ZengNC12,
author = {Chen Zeng and
Jeffrey F. Naughton and
Jin{-}Yi Cai},
title = {On differentially private frequent itemset mining},
journal = {Proc. {VLDB} Endow.},
volume = {6},
number = {1},
pages = {25--36},
year = {2012},
url = {https://doi.org/10.14778/2428536.2428539},
doi = {10.14778/2428536.2428539},
timestamp = {Thu, 13 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/pvldb/ZengNC12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/CaiK12,
author = {Jin{-}Yi Cai and
Michael Kowalczyk},
title = {Spin systems on k-regular graphs with complex edge functions},
journal = {Theor. Comput. Sci.},
volume = {461},
pages = {2--16},
year = {2012},
url = {https://doi.org/10.1016/j.tcs.2012.01.021},
doi = {10.1016/J.TCS.2012.01.021},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/CaiK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoa/CaiCGL12,
author = {Jin{-}Yi Cai and
Xi Chen and
Heng Guo and
Pinyan Lu},
editor = {Guohui Lin},
title = {Inapproximability after Uniqueness Phase Transition in Two-Spin Systems},
booktitle = {Combinatorial Optimization and Applications - 6th International Conference,
{COCOA} 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7402},
pages = {336--347},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-31770-5\_30},
doi = {10.1007/978-3-642-31770-5\_30},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/cocoa/CaiCGL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/CaiKW12,
author = {Jin{-}yi Cai and
Michael Kowalczyk and
Tyson Williams},
editor = {Shafi Goldwasser},
title = {Gadgets and anti-gadgets leading to a complexity dichotomy},
booktitle = {Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA,
January 8-10, 2012},
pages = {452--467},
publisher = {{ACM}},
year = {2012},
url = {https://doi.org/10.1145/2090236.2090272},
doi = {10.1145/2090236.2090272},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/CaiKW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CaiC12,
author = {Jin{-}Yi Cai and
Xi Chen},
editor = {Howard J. Karloff and
Toniann Pitassi},
title = {Complexity of counting {CSP} with complex weights},
booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference,
{STOC} 2012, New York, NY, USA, May 19 - 22, 2012},
pages = {909--920},
publisher = {{ACM}},
year = {2012},
url = {https://doi.org/10.1145/2213977.2214059},
doi = {10.1145/2213977.2214059},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CaiC12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tamc/FuC12,
author = {Zhiguo Fu and
Jin{-}Yi Cai},
editor = {Manindra Agrawal and
S. Barry Cooper and
Angsheng Li},
title = {Holographic Algorithms on Domain Size k {\textgreater} 2},
booktitle = {Theory and Applications of Models of Computation - 9th Annual Conference,
{TAMC} 2012, Beijing, China, May 16-21, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7287},
pages = {346--359},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-29952-0\_35},
doi = {10.1007/978-3-642-29952-0\_35},
timestamp = {Tue, 14 May 2019 10:00:46 +0200},
biburl = {https://dblp.org/rec/conf/tamc/FuC12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1204-6445,
author = {Jin{-}Yi Cai and
Heng Guo and
Tyson Williams},
title = {A Complete Dichotomy Rises from the Capture of Vanishing Signatures},
journal = {CoRR},
volume = {abs/1204.6445},
year = {2012},
url = {http://arxiv.org/abs/1204.6445},
eprinttype = {arXiv},
eprint = {1204.6445},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1204-6445.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1205-2934,
author = {Jin{-}Yi Cai and
Xi Chen and
Heng Guo and
Pinyan Lu},
title = {Inapproximability After Uniqueness Phase Transition in Two-Spin Systems},
journal = {CoRR},
volume = {abs/1205.2934},
year = {2012},
url = {http://arxiv.org/abs/1205.2934},
eprinttype = {arXiv},
eprint = {1205.2934},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1205-2934.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1207-2354,
author = {Jin{-}Yi Cai and
Pinyan Lu and
Mingji Xia},
title = {Dichotomy for Holant* Problems with a Function on Domain Size 3},
journal = {CoRR},
volume = {abs/1207.2354},
year = {2012},
url = {http://arxiv.org/abs/1207.2354},
eprinttype = {arXiv},
eprint = {1207.2354},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1207-2354.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/CaiL11,
author = {Jin{-}yi Cai and
Pinyan Lu},
title = {Signature Theory in Holographic Algorithms},
journal = {Algorithmica},
volume = {61},
number = {4},
pages = {779--816},
year = {2011},
url = {https://doi.org/10.1007/s00453-009-9383-3},
doi = {10.1007/S00453-009-9383-3},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/CaiL11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jco/ZhangCTZ11,
author = {Peng Zhang and
Jin{-}yi Cai and
Linqing Tang and
Wenbo Zhao},
title = {Approximation and hardness results for label cut and related problems},
journal = {J. Comb. Optim.},
volume = {21},
number = {2},
pages = {192--208},
year = {2011},
url = {https://doi.org/10.1007/s10878-009-9222-0},
doi = {10.1007/S10878-009-9222-0},
timestamp = {Thu, 07 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jco/ZhangCTZ11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jco/CaiYAB11,
author = {Jin{-}yi Cai and
Vinod Yegneswaran and
Chris Alfeld and
Paul Barford},
title = {Honeynet games: a game theoretic approach to defending network monitors},
journal = {J. Comb. Optim.},
volume = {22},
number = {3},
pages = {305--324},
year = {2011},
url = {https://doi.org/10.1007/s10878-009-9285-y},
doi = {10.1007/S10878-009-9285-Y},
timestamp = {Thu, 18 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jco/CaiYAB11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/CaiS11,
author = {Jin{-}yi Cai and
Alan L. Selman},
title = {Foreword},
journal = {J. Comput. Syst. Sci.},
volume = {77},
number = {1},
pages = {1--2},
year = {2011},
url = {https://doi.org/10.1016/j.jcss.2010.06.015},
doi = {10.1016/J.JCSS.2010.06.015},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/CaiS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/CaiL11,
author = {Jin{-}yi Cai and
Pinyan Lu},
title = {Holographic algorithms: From art to science},
journal = {J. Comput. Syst. Sci.},
volume = {77},
number = {1},
pages = {41--61},
year = {2011},
url = {https://doi.org/10.1016/j.jcss.2010.06.005},
doi = {10.1016/J.JCSS.2010.06.005},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jcss/CaiL11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiLX11,
author = {Jin{-}yi Cai and
Pinyan Lu and
Mingji Xia},
title = {Computational Complexity of Holant Problems},
journal = {{SIAM} J. Comput.},
volume = {40},
number = {4},
pages = {1101--1132},
year = {2011},
url = {https://doi.org/10.1137/100814585},
doi = {10.1137/100814585},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiLX11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/CaiLX11,
author = {Jin{-}yi Cai and
Pinyan Lu and
Mingji Xia},
title = {A computational proof of complexity of some restricted counting problems},
journal = {Theor. Comput. Sci.},
volume = {412},
number = {23},
pages = {2468--2485},
year = {2011},
url = {https://doi.org/10.1016/j.tcs.2010.10.039},
doi = {10.1016/J.TCS.2010.10.039},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/CaiLX11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/aaim/Cai11,
author = {Jin{-}yi Cai},
editor = {Mikhail J. Atallah and
Xiang{-}Yang Li and
Binhai Zhu},
title = {Progress in Complexity of Counting Problems},
booktitle = {Frontiers in Algorithmics and Algorithmic Aspects in Information and
Management - Joint International Conference, {FAW-AAIM} 2011, Jinhua,
China, May 28-31, 2011. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6681},
pages = {1--3},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-21204-8\_1},
doi = {10.1007/978-3-642-21204-8\_1},
timestamp = {Tue, 14 May 2019 10:00:41 +0200},
biburl = {https://dblp.org/rec/conf/aaim/Cai11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiCL11,
author = {Jin{-}yi Cai and
Xi Chen and
Pinyan Lu},
title = {Non-negatively Weighted {\#}CSP: An Effective Complexity Dichotomy},
booktitle = {Proceedings of the 26th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2011, San Jose, California, USA, June 8-10, 2011},
pages = {45--54},
publisher = {{IEEE} Computer Society},
year = {2011},
url = {https://doi.org/10.1109/CCC.2011.32},
doi = {10.1109/CCC.2011.32},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/CaiCL11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/CaiK11,
author = {Jin{-}yi Cai and
Michael Kowalczyk},
editor = {Bin Fu and
Ding{-}Zhu Du},
title = {Spin Systems on Graphs with Complex Edge Functions and Specified Degree
Regularities},
booktitle = {Computing and Combinatorics - 17th Annual International Conference,
{COCOON} 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6842},
pages = {146--157},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22685-4\_13},
doi = {10.1007/978-3-642-22685-4\_13},
timestamp = {Tue, 14 May 2019 10:00:35 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/CaiK11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CaiLX11,
author = {Jin{-}yi Cai and
Pinyan Lu and
Mingji Xia},
editor = {Dana Randall},
title = {Dichotomy for Holant* Problems of Boolean Domain},
booktitle = {Proceedings of the Twenty-Second Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2011, San Francisco, California, USA, January 23-25,
2011},
pages = {1714--1728},
publisher = {{SIAM}},
year = {2011},
url = {https://doi.org/10.1137/1.9781611973082.132},
doi = {10.1137/1.9781611973082.132},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/CaiLX11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1108-3383,
author = {Jin{-}yi Cai and
Michael Kowalczyk and
Tyson Williams},
title = {Gadgets and Anti-gadgets Leading to a Complexity Dichotomy},
journal = {CoRR},
volume = {abs/1108.3383},
year = {2011},
url = {http://arxiv.org/abs/1108.3383},
eprinttype = {arXiv},
eprint = {1108.3383},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1108-3383.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1111-2384,
author = {Jin{-}yi Cai and
Xi Chen},
title = {Complexity of Counting {CSP} with Complex Weights},
journal = {CoRR},
volume = {abs/1111.2384},
year = {2011},
url = {http://arxiv.org/abs/1111.2384},
eprinttype = {arXiv},
eprint = {1111.2384},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1111-2384.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/CaiCL10,
author = {Jin{-}yi Cai and
Xi Chen and
Dong Li},
title = {Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic},
journal = {Comput. Complex.},
volume = {19},
number = {1},
pages = {37--56},
year = {2010},
url = {https://doi.org/10.1007/s00037-009-0284-2},
doi = {10.1007/S00037-009-0284-2},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/CaiCL10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/CaiL10,
author = {Jin{-}yi Cai and
Pinyan Lu},
title = {On Symmetric Signatures in Holographic Algorithms},
journal = {Theory Comput. Syst.},
volume = {46},
number = {3},
pages = {398--415},
year = {2010},
url = {https://doi.org/10.1007/s00224-009-9229-z},
doi = {10.1007/S00224-009-9229-Z},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/CaiL10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/CaiL10,
author = {Jin{-}yi Cai and
Pinyan Lu},
title = {On blockwise symmetric signatures for matchgates},
journal = {Theor. Comput. Sci.},
volume = {411},
number = {4-5},
pages = {739--750},
year = {2010},
url = {https://doi.org/10.1016/j.tcs.2009.10.012},
doi = {10.1016/J.TCS.2009.10.012},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/CaiL10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/faw/CaiCLL10,
author = {Jin{-}yi Cai and
Xi Chen and
Richard J. Lipton and
Pinyan Lu},
editor = {Der{-}Tsai Lee and
Danny Z. Chen and
Shi Ying},
title = {On Tractable Exponential Sums},
booktitle = {Frontiers in Algorithmics, 4th International Workshop, {FAW} 2010,
Wuhan, China, August 11-13, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6213},
pages = {148--159},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-14553-7\_16},
doi = {10.1007/978-3-642-14553-7\_16},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/faw/CaiCLL10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiLX10,
author = {Jin{-}yi Cai and
Pinyan Lu and
Mingji Xia},
title = {Holographic Algorithms with Matchgates Capture Precisely Tractable
Planar{\_}{\#}CSP},
booktitle = {51th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2010, October 23-26, 2010, Las Vegas, Nevada, {USA}},
pages = {427--436},
publisher = {{IEEE} Computer Society},
year = {2010},
url = {https://doi.org/10.1109/FOCS.2010.48},
doi = {10.1109/FOCS.2010.48},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/CaiLX10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiC10,
author = {Jin{-}yi Cai and
Xi Chen},
title = {A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with
Non-negative Weights},
booktitle = {51th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2010, October 23-26, 2010, Las Vegas, Nevada, {USA}},
pages = {437--446},
publisher = {{IEEE} Computer Society},
year = {2010},
url = {https://doi.org/10.1109/FOCS.2010.49},
doi = {10.1109/FOCS.2010.49},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CaiC10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/CaiCL10,
author = {Jin{-}yi Cai and
Xi Chen and
Pinyan Lu},
editor = {Samson Abramsky and
Cyril Gavoille and
Claude Kirchner and
Friedhelm Meyer auf der Heide and
Paul G. Spirakis},
title = {Graph Homomorphisms with Complex Values: {A} Dichotomy Theorem},
booktitle = {Automata, Languages and Programming, 37th International Colloquium,
{ICALP} 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {6198},
pages = {275--286},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-14165-2\_24},
doi = {10.1007/978-3-642-14165-2\_24},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/CaiCL10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isaac/CaiHL10,
author = {Jin{-}yi Cai and
Sangxia Huang and
Pinyan Lu},
editor = {Otfried Cheong and
Kyung{-}Yong Chwa and
Kunsoo Park},
title = {From Holant to {\#}CSP and Back: Dichotomy for Holant\({}^{\mbox{\emph{c}}}\)
Problems},
booktitle = {Algorithms and Computation - 21st International Symposium, {ISAAC}
2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {6506},
pages = {253--265},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-17517-6\_24},
doi = {10.1007/978-3-642-17517-6\_24},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/isaac/CaiHL10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/KowalczykC10,
author = {Michael Kowalczyk and
Jin{-}yi Cai},
editor = {Jean{-}Yves Marion and
Thomas Schwentick},
title = {Holant Problems for Regular Graphs with Complex Edge Functions},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science,
{STACS} 2010, March 4-6, 2010, Nancy, France},
series = {LIPIcs},
volume = {5},
pages = {525--536},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2010},
url = {https://doi.org/10.4230/LIPIcs.STACS.2010.2482},
doi = {10.4230/LIPICS.STACS.2010.2482},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/stacs/KowalczykC10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tamc/CaiK10,
author = {Jin{-}yi Cai and
Michael Kowalczyk},
editor = {Jan Kratochv{\'{\i}}l and
Angsheng Li and
Jir{\'{\i}} Fiala and
Petr Kolman},
title = {A Dichotomy for \emph{k}-Regular Graphs with \{0, 1\}-Vertex Assignments
and Real Edge Functions},
booktitle = {Theory and Applications of Models of Computation, 7th Annual Conference,
{TAMC} 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6108},
pages = {328--339},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-13562-0\_30},
doi = {10.1007/978-3-642-13562-0\_30},
timestamp = {Tue, 14 May 2019 10:00:46 +0200},
biburl = {https://dblp.org/rec/conf/tamc/CaiK10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1001-0464,
author = {Michael Kowalczyk and
Jin{-}yi Cai},
title = {Holant Problems for Regular Graphs with Complex Edge Functions},
journal = {CoRR},
volume = {abs/1001.0464},
year = {2010},
url = {http://arxiv.org/abs/1001.0464},
eprinttype = {arXiv},
eprint = {1001.0464},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1001-0464.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1004-0803,
author = {Jin{-}yi Cai and
Sangxia Huang and
Pinyan Lu},
title = {From Holant To {\#}CSP And Back: Dichotomy For Holant{\textdollar}{\^{}}c{\textdollar}
Problems},
journal = {CoRR},
volume = {abs/1004.0803},
year = {2010},
url = {http://arxiv.org/abs/1004.0803},
eprinttype = {arXiv},
eprint = {1004.0803},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1004-0803.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1005-2632,
author = {Jin{-}yi Cai and
Xi Chen and
Richard J. Lipton and
Pinyan Lu},
title = {On Tractable Exponential Sums},
journal = {CoRR},
volume = {abs/1005.2632},
year = {2010},
url = {http://arxiv.org/abs/1005.2632},
eprinttype = {arXiv},
eprint = {1005.2632},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1005-2632.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1008-0683,
author = {Jin{-}yi Cai and
Pinyan Lu and
Mingji Xia},
title = {Holographic Algorithms with Matchgates Capture Precisely Tractable
Planar {\#}CSP},
journal = {CoRR},
volume = {abs/1008.0683},
year = {2010},
url = {http://arxiv.org/abs/1008.0683},
eprinttype = {arXiv},
eprint = {1008.0683},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1008-0683.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1008-0915,
author = {Jin{-}yi Cai and
Xi Chen},
title = {A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with
Non-negative Weights},
journal = {CoRR},
volume = {abs/1008.0915},
year = {2010},
url = {http://arxiv.org/abs/1008.0915},
eprinttype = {arXiv},
eprint = {1008.0915},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1008-0915.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1012-5659,
author = {Jin{-}yi Cai and
Xi Chen and
Pinyan Lu},
title = {Non-negative Weighted {\#}CSPs: An Effective Complexity Dichotomy},
journal = {CoRR},
volume = {abs/1012.5659},
year = {2010},
url = {http://arxiv.org/abs/1012.5659},
eprinttype = {arXiv},
eprint = {1012.5659},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1012-5659.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cominfsys/BachC09,
author = {Eric Bach and
Jin{-}Yi Cai},
title = {A Novel Information Transmission Problem and its Optimal Solution},
journal = {Commun. Inf. Syst.},
volume = {9},
number = {2},
pages = {141--162},
year = {2009},
url = {https://doi.org/10.4310/cis.2009.v9.n2.a1},
doi = {10.4310/CIS.2009.V9.N2.A1},
timestamp = {Wed, 01 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cominfsys/BachC09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mscs/CaiCL09,
author = {Jin{-}yi Cai and
S. Barry Cooper and
Angsheng Li},
title = {Preface to Special Issue: Theory and Applications of Models of Computation
{(TAMC)}},
journal = {Math. Struct. Comput. Sci.},
volume = {19},
number = {1},
pages = {5--7},
year = {2009},
url = {https://doi.org/10.1017/S0960129508007214},
doi = {10.1017/S0960129508007214},
timestamp = {Wed, 01 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mscs/CaiCL09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/CaiCL09,
author = {Jin{-}yi Cai and
Vinay Choudhary and
Pinyan Lu},
title = {On the Theory of Matchgate Computations},
journal = {Theory Comput. Syst.},
volume = {45},
number = {1},
pages = {108--132},
year = {2009},
url = {https://doi.org/10.1007/s00224-007-9092-8},
doi = {10.1007/S00224-007-9092-8},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/CaiCL09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/CaiL09,
author = {Jin{-}yi Cai and
Pinyan Lu},
title = {Holographic algorithms: The power of dimensionality resolved},
journal = {Theor. Comput. Sci.},
volume = {410},
number = {18},
pages = {1618--1628},
year = {2009},
url = {https://doi.org/10.1016/j.tcs.2008.12.047},
doi = {10.1016/J.TCS.2008.12.047},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/CaiL09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/CaiYAB09,
author = {Jin{-}yi Cai and
Vinod Yegneswaran and
Chris Alfeld and
Paul Barford},
editor = {Hung Q. Ngo},
title = {An Attacker-Defender Game for Honeynets},
booktitle = {Computing and Combinatorics, 15th Annual International Conference,
{COCOON} 2009, Niagara Falls, NY, USA, July 13-15, 2009, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5609},
pages = {7--16},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-02882-3\_2},
doi = {10.1007/978-3-642-02882-3\_2},
timestamp = {Tue, 14 May 2019 10:00:35 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/CaiYAB09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CaiLX09,
author = {Jin{-}yi Cai and
Pinyan Lu and
Mingji Xia},
editor = {Michael Mitzenmacher},
title = {Holant problems and counting {CSP}},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {715--724},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536511},
doi = {10.1145/1536414.1536511},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/CaiLX09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tamc/CaiLX09,
author = {Jin{-}yi Cai and
Pinyan Lu and
Mingji Xia},
editor = {Jianer Chen and
S. Barry Cooper},
title = {A Computational Proof of Complexity of Some Restricted Counting Problems},
booktitle = {Theory and Applications of Models of Computation, 6th Annual Conference,
{TAMC} 2009, Changsha, China, May 18-22, 2009. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5532},
pages = {138--149},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-02017-9\_17},
doi = {10.1007/978-3-642-02017-9\_17},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/tamc/CaiLX09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tamc/ZhangCTZ09,
author = {Peng Zhang and
Jin{-}yi Cai and
Linqing Tang and
Wenbo Zhao},
editor = {Jianer Chen and
S. Barry Cooper},
title = {Approximation and Hardness Results for Label Cut and Related Problems},
booktitle = {Theory and Applications of Models of Computation, 6th Annual Conference,
{TAMC} 2009, Changsha, China, May 18-22, 2009. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5532},
pages = {460--469},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-02017-9\_48},
doi = {10.1007/978-3-642-02017-9\_48},
timestamp = {Thu, 07 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/tamc/ZhangCTZ09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0903-4728,
author = {Jin{-}yi Cai and
Xi Chen and
Pinyan Lu},
title = {Graph Homomorphisms with Complex Values: {A} Dichotomy Theorem},
journal = {CoRR},
volume = {abs/0903.4728},
year = {2009},
url = {http://arxiv.org/abs/0903.4728},
eprinttype = {arXiv},
eprint = {0903.4728},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0903-4728.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/CaiL08,
author = {Jin{-}yi Cai and
Pinyan Lu},
title = {Basis Collapse in Holographic Algorithms},
journal = {Comput. Complex.},
volume = {17},
number = {2},
pages = {254--281},
year = {2008},
url = {https://doi.org/10.1007/s00037-008-0249-x},
doi = {10.1007/S00037-008-0249-X},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/CaiL08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/sigact/Cai08,
author = {Jin{-}yi Cai},
title = {Holographic algorithms: guest column},
journal = {{SIGACT} News},
volume = {39},
number = {2},
pages = {51--81},
year = {2008},
url = {https://doi.org/10.1145/1388240.1388254},
doi = {10.1145/1388240.1388254},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/sigact/Cai08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiLX08,
author = {Jin{-}yi Cai and
Pinyan Lu and
Mingji Xia},
title = {Holographic Algorithms by Fibonacci Gates and Holographic Reductions
for Hardness},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {644--653},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.34},
doi = {10.1109/FOCS.2008.34},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/CaiLX08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isaac/CaiL08,
author = {Jin{-}yi Cai and
Pinyan Lu},
editor = {Seok{-}Hee Hong and
Hiroshi Nagamochi and
Takuro Fukunaga},
title = {Signature Theory in Holographic Algorithms},
booktitle = {Algorithms and Computation, 19th International Symposium, {ISAAC}
2008, Gold Coast, Australia, December 15-17, 2008. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5369},
pages = {568--579},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-92182-0\_51},
doi = {10.1007/978-3-540-92182-0\_51},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/isaac/CaiL08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CaiL08,
author = {Jin{-}yi Cai and
Pinyan Lu},
editor = {Shang{-}Hua Teng},
title = {Holographic algorithms with unsymmetric signatures},
booktitle = {Proceedings of the Nineteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2008, San Francisco, California, USA, January 20-22,
2008},
pages = {54--63},
publisher = {{SIAM}},
year = {2008},
url = {http://dl.acm.org/citation.cfm?id=1347082.1347089},
timestamp = {Fri, 07 Dec 2012 17:02:08 +0100},
biburl = {https://dblp.org/rec/conf/soda/CaiL08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CaiCL08,
author = {Jin{-}yi Cai and
Xi Chen and
Dong Li},
editor = {Cynthia Dwork},
title = {A quadratic lower bound for the permanent and determinant problem
over any characteristic != 2},
booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
Victoria, British Columbia, Canada, May 17-20, 2008},
pages = {491--498},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1374376.1374446},
doi = {10.1145/1374376.1374446},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CaiCL08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0801-1766,
author = {Jin{-}yi Cai and
Pinyan Lu and
Mingji Xia},
title = {A Family of Counter Examples to an Approach to Graph Isomorphism},
journal = {CoRR},
volume = {abs/0801.1766},
year = {2008},
url = {http://arxiv.org/abs/0801.1766},
eprinttype = {arXiv},
eprint = {0801.1766},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0801-1766.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ijsi/CaiC07,
author = {Jin{-}yi Cai and
Vinay Choudhary},
title = {Some Results on Matchgates and Holographic Algorithms},
journal = {Int. J. Softw. Informatics},
volume = {1},
number = {1},
pages = {3--36},
year = {2007},
url = {http://www.ijsi.org/ch/reader/view\_abstract.aspx?file\_no=20073},
timestamp = {Thu, 06 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ijsi/CaiC07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/Cai07,
author = {Jin{-}yi Cai},
title = {S\({}_{\mbox{2}}\)\({}^{\mbox{p}}\) is subset of ZPP\({}^{\mbox{NP}}\)},
journal = {J. Comput. Syst. Sci.},
volume = {73},
number = {1},
pages = {25--35},
year = {2007},
url = {https://doi.org/10.1016/j.jcss.2003.07.015},
doi = {10.1016/J.JCSS.2003.07.015},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/Cai07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/CaiC07,
author = {Jin{-}yi Cai and
Vinay Choudhary},
title = {Valiant's Holant Theorem and matchgate tensors},
journal = {Theor. Comput. Sci.},
volume = {384},
number = {1},
pages = {22--32},
year = {2007},
url = {https://doi.org/10.1016/j.tcs.2007.05.015},
doi = {10.1016/J.TCS.2007.05.015},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/CaiC07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiL07,
author = {Jin{-}yi Cai and
Pinyan Lu},
title = {Bases Collapse in Holographic Algorithms},
booktitle = {22nd Annual {IEEE} Conference on Computational Complexity {(CCC} 2007),
13-16 June 2007, San Diego, California, {USA}},
pages = {292--304},
publisher = {{IEEE} Computer Society},
year = {2007},
url = {https://doi.org/10.1109/CCC.2007.6},
doi = {10.1109/CCC.2007.6},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/CaiL07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiCL07,
author = {Jin{-}yi Cai and
Vinay Choudhary and
Pinyan Lu},
title = {On the Theory of Matchgate Computations},
booktitle = {22nd Annual {IEEE} Conference on Computational Complexity {(CCC} 2007),
13-16 June 2007, San Diego, California, {USA}},
pages = {305--318},
publisher = {{IEEE} Computer Society},
year = {2007},
url = {https://doi.org/10.1109/CCC.2007.22},
doi = {10.1109/CCC.2007.22},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/CaiCL07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fct/BachC07,
author = {Eric Bach and
Jin{-}yi Cai},
editor = {Erzs{\'{e}}bet Csuhaj{-}Varj{\'{u}} and
Zolt{\'{a}}n {\'{E}}sik},
title = {A Novel Information Transmission Problem and Its Optimal Solution},
booktitle = {Fundamentals of Computation Theory, 16th International Symposium,
{FCT} 2007, Budapest, Hungary, August 27-30, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4639},
pages = {64--75},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74240-1\_7},
doi = {10.1007/978-3-540-74240-1\_7},
timestamp = {Wed, 01 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/fct/BachC07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fct/CaiL07,
author = {Jin{-}yi Cai and
Pinyan Lu},
editor = {Erzs{\'{e}}bet Csuhaj{-}Varj{\'{u}} and
Zolt{\'{a}}n {\'{E}}sik},
title = {On Block-Wise Symmetric Signatures for Matchgates},
booktitle = {Fundamentals of Computation Theory, 16th International Symposium,
{FCT} 2007, Budapest, Hungary, August 27-30, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4639},
pages = {187--198},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74240-1\_17},
doi = {10.1007/978-3-540-74240-1\_17},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/fct/CaiL07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/CaiL07,
author = {Jin{-}yi Cai and
Pinyan Lu},
editor = {Lars Arge and
Christian Cachin and
Tomasz Jurdzinski and
Andrzej Tarlecki},
title = {Holographic Algorithms: The Power of Dimensionality Resolved},
booktitle = {Automata, Languages and Programming, 34th International Colloquium,
{ICALP} 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4596},
pages = {631--642},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-73420-8\_55},
doi = {10.1007/978-3-540-73420-8\_55},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/CaiL07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/kdd/GaoESCX07,
author = {Byron J. Gao and
Martin Ester and
Jin{-}yi Cai and
Oliver Schulte and
Hui Xiong},
editor = {Pavel Berkhin and
Rich Caruana and
Xindong Wu},
title = {The minimum consistent subset cover problem and its applications in
data mining},
booktitle = {Proceedings of the 13th {ACM} {SIGKDD} International Conference on
Knowledge Discovery and Data Mining, San Jose, California, USA, August
12-15, 2007},
pages = {310--319},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1281192.1281228},
doi = {10.1145/1281192.1281228},
timestamp = {Fri, 10 Mar 2023 14:55:31 +0100},
biburl = {https://dblp.org/rec/conf/kdd/GaoESCX07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/CaiL07,
author = {Jin{-}yi Cai and
Pinyan Lu},
editor = {Wolfgang Thomas and
Pascal Weil},
title = {On Symmetric Signatures in Holographic Algorithms},
booktitle = {{STACS} 2007, 24th Annual Symposium on Theoretical Aspects of Computer
Science, Aachen, Germany, February 22-24, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4393},
pages = {429--440},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-70918-3\_37},
doi = {10.1007/978-3-540-70918-3\_37},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stacs/CaiL07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CaiL07,
author = {Jin{-}yi Cai and
Pinyan Lu},
editor = {David S. Johnson and
Uriel Feige},
title = {Holographic algorithms: from art to science},
booktitle = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
pages = {401--410},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1250790.1250850},
doi = {10.1145/1250790.1250850},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/CaiL07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/tamc/2007,
editor = {Jin{-}yi Cai and
S. Barry Cooper and
Hong Zhu},
title = {Theory and Applications of Models of Computation, 4th International
Conference, {TAMC} 2007, Shanghai, China, May 22-25, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4484},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-72504-6},
doi = {10.1007/978-3-540-72504-6},
isbn = {978-3-540-72503-9},
timestamp = {Mon, 04 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/tamc/2007.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CaiL07,
author = {Jin{-}yi Cai and
Pinyan Lu},
title = {Bases Collapse in Holographic Algorithms},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-003}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-003/index.html},
eprinttype = {ECCC},
eprint = {TR07-003},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CaiL07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CaiL07a,
author = {Jin{-}yi Cai and
Pinyan Lu},
title = {On Block-wise Symmetric Signatures for Matchgates},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-019}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-019/index.html},
eprinttype = {ECCC},
eprint = {TR07-019},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CaiL07a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CaiL07b,
author = {Jin{-}yi Cai and
Pinyan Lu},
title = {Holographic Algorithms: The Power of Dimensionality Resolved},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-020}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-020/index.html},
eprinttype = {ECCC},
eprint = {TR07-020},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CaiL07b.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/CaiW06,
author = {Jin{-}yi Cai and
Osamu Watanabe},
title = {Random Access to Advice Strings and Collapsing Results},
journal = {Algorithmica},
volume = {46},
number = {1},
pages = {43--57},
year = {2006},
url = {https://doi.org/10.1007/s00453-006-0078-8},
doi = {10.1007/S00453-006-0078-8},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/CaiW06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jco/CaiC06,
author = {Jin{-}yi Cai and
Venkatesan T. Chakaravarthy},
title = {On zero error algorithms having oracle access to one query},
journal = {J. Comb. Optim.},
volume = {11},
number = {2},
pages = {189--202},
year = {2006},
url = {https://doi.org/10.1007/s10878-006-7130-0},
doi = {10.1007/S10878-006-7130-0},
timestamp = {Thu, 18 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jco/CaiC06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/CaiCM06,
author = {Jin{-}yi Cai and
Venkatesan T. Chakaravarthy and
Dieter van Melkebeek},
title = {Time-Space Tradeoff in Derandomizing Probabilistic Logspace},
journal = {Theory Comput. Syst.},
volume = {39},
number = {1},
pages = {189--208},
year = {2006},
url = {https://doi.org/10.1007/s00224-005-1264-9},
doi = {10.1007/S00224-005-1264-9},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/CaiCM06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/CaiC06,
author = {Jin{-}yi Cai and
Vinay Choudhary},
editor = {Michele Bugliesi and
Bart Preneel and
Vladimiro Sassone and
Ingo Wegener},
title = {Some Results on Matchgates and Holographic Algorithms},
booktitle = {Automata, Languages and Programming, 33rd International Colloquium,
{ICALP} 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {4051},
pages = {703--714},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11786986\_61},
doi = {10.1007/11786986\_61},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/CaiC06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tamc/CaiC06,
author = {Jin{-}yi Cai and
Vinay Choudhary},
editor = {Jin{-}yi Cai and
S. Barry Cooper and
Angsheng Li},
title = {Valiant's Holant Theorem and Matchgate Tensors},
booktitle = {Theory and Applications of Models of Computation, Third International
Conference, {TAMC} 2006, Beijing, China, May 15-20, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3959},
pages = {248--261},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11750321\_24},
doi = {10.1007/11750321\_24},
timestamp = {Tue, 14 May 2019 10:00:46 +0200},
biburl = {https://dblp.org/rec/conf/tamc/CaiC06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/tamc/2006,
editor = {Jin{-}yi Cai and
S. Barry Cooper and
Angsheng Li},
title = {Theory and Applications of Models of Computation, Third International
Conference, {TAMC} 2006, Beijing, China, May 15-20, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3959},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11750321},
doi = {10.1007/11750321},
isbn = {3-540-34021-1},
timestamp = {Tue, 14 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/tamc/2006.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CaiC06,
author = {Jin{-}yi Cai and
Vinay Choudhary},
title = {Some Results on Matchgates and Holographic Algorithms},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-048}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-048/index.html},
eprinttype = {ECCC},
eprint = {TR06-048},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CaiC06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CaiL06,
author = {Jin{-}yi Cai and
Pinyan Lu},
title = {On Symmetric Signatures in Holographic Algorithms},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-135}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-135/index.html},
eprinttype = {ECCC},
eprint = {TR06-135},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CaiL06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CaiL06a,
author = {Jin{-}yi Cai and
Pinyan Lu},
title = {Holographic Algorithms: From Art to Science},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-145}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-145/index.html},
eprinttype = {ECCC},
eprint = {TR06-145},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CaiL06a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR06-018,
author = {Jin{-}yi Cai and
Vinay Choudhary},
title = {On the Theory of Matchgate Computations},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-018}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-018/index.html},
eprinttype = {ECCC},
eprint = {TR06-018},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR06-018.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/CaiCHO05,
author = {Jin{-}yi Cai and
Venkatesan T. Chakaravarthy and
Lane A. Hemaspaandra and
Mitsunori Ogihara},
title = {Competing provers yield improved Karp-Lipton collapse results},
journal = {Inf. Comput.},
volume = {198},
number = {1},
pages = {1--23},
year = {2005},
url = {https://doi.org/10.1016/j.ic.2005.01.002},
doi = {10.1016/J.IC.2005.01.002},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/CaiCHO05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcst/CaiZ05,
author = {Jin{-}yi Cai and
Hong Zhu},
title = {Progress in Computational Complexity Theory},
journal = {J. Comput. Sci. Technol.},
volume = {20},
number = {6},
pages = {735--750},
year = {2005},
url = {https://doi.org/10.1007/s11390-005-0735-4},
doi = {10.1007/S11390-005-0735-4},
timestamp = {Mon, 04 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jcst/CaiZ05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/CaiC05,
author = {Jin{-}yi Cai and
Venkatesan T. Chakaravarthy},
editor = {Lusheng Wang},
title = {A Note on Zero Error Algorithms Having Oracle Access to One {NP} Query},
booktitle = {Computing and Combinatorics, 11th Annual International Conference,
{COCOON} 2005, Kunming, China, August 16-29, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3595},
pages = {339--348},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11533719\_35},
doi = {10.1007/11533719\_35},
timestamp = {Tue, 14 May 2019 10:00:35 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/CaiC05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isaac/LuZPC05,
author = {Pinyan Lu and
Jialin Zhang and
Chung Keung Poon and
Jin{-}yi Cai},
editor = {Xiaotie Deng and
Ding{-}Zhu Du},
title = {Simulating Undirected \emph{st}-Connectivity Algorithms on Uniform
JAGs and NNJAGs},
booktitle = {Algorithms and Computation, 16th International Symposium, {ISAAC}
2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3827},
pages = {767--776},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11602613\_77},
doi = {10.1007/11602613\_77},
timestamp = {Tue, 17 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/isaac/LuZPC05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR05-118,
author = {Jin{-}yi Cai and
Vinay Choudhary},
title = {Valiant's Holant Theorem and Matchgate Tensors},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR05-118}},
year = {2005},
url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-118/index.html},
eprinttype = {ECCC},
eprint = {TR05-118},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-118.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ijfcs/CaiCPS04,
author = {Jin{-}yi Cai and
Denis Charles and
Aduri Pavan and
Samik Sengupta},
title = {On Higher Arthur-Merlin Classes},
journal = {Int. J. Found. Comput. Sci.},
volume = {15},
number = {1},
pages = {3--19},
year = {2004},
url = {https://doi.org/10.1142/S0129054104002273},
doi = {10.1142/S0129054104002273},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ijfcs/CaiCPS04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/CaiW04,
author = {Jin{-}yi Cai and
Osamu Watanabe},
title = {Relativized collapsing between {BPP} and {PH} under stringent oracle
access},
journal = {Inf. Process. Lett.},
volume = {90},
number = {3},
pages = {147--154},
year = {2004},
url = {https://doi.org/10.1016/j.ipl.2004.02.004},
doi = {10.1016/J.IPL.2004.02.004},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/CaiW04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/CaiT04,
author = {Jin{-}yi Cai and
Robert A. Threlfall},
title = {A note on quadratic residuosity and {UP}},
journal = {Inf. Process. Lett.},
volume = {92},
number = {3},
pages = {127--131},
year = {2004},
url = {https://doi.org/10.1016/j.ipl.2004.06.015},
doi = {10.1016/J.IPL.2004.06.015},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/CaiT04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiW04,
author = {Jin{-}yi Cai and
Osamu Watanabe},
title = {On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy},
journal = {{SIAM} J. Comput.},
volume = {33},
number = {4},
pages = {984--1009},
year = {2004},
url = {https://doi.org/10.1137/S0097539703422716},
doi = {10.1137/S0097539703422716},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiW04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icdm/HuangCCGMRSW04,
author = {Zheng Huang and
Lei Chen and
Jin{-}yi Cai and
Deborah S. Gross and
David R. Musicant and
Raghu Ramakrishnan and
James J. Schauer and
Stephen J. Wright},
title = {Mass Spectrum Labeling: Theory and Practice},
booktitle = {Proceedings of the 4th {IEEE} International Conference on Data Mining
{(ICDM} 2004), 1-4 November 2004, Brighton, {UK}},
pages = {122--129},
publisher = {{IEEE} Computer Society},
year = {2004},
url = {https://doi.org/10.1109/ICDM.2004.10080},
doi = {10.1109/ICDM.2004.10080},
timestamp = {Tue, 07 May 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icdm/HuangCCGMRSW04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isaac/CaiW04,
author = {Jin{-}yi Cai and
Osamu Watanabe},
editor = {Rudolf Fleischer and
Gerhard Trippen},
title = {Random Access to Advice Strings and Collapsing Results},
booktitle = {Algorithms and Computation, 15th International Symposium, {ISAAC}
2004, Hong Kong, China, December 20-22, 2004, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3341},
pages = {209--220},
publisher = {Springer},
year = {2004},
url = {https://doi.org/10.1007/978-3-540-30551-4\_20},
doi = {10.1007/978-3-540-30551-4\_20},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/isaac/CaiW04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/CaiCM04,
author = {Jin{-}yi Cai and
Venkatesan T. Chakaravarthy and
Dieter van Melkebeek},
editor = {Volker Diekert and
Michel Habib},
title = {Time-Space Tradeoff in Derandomizing Probabilistic Logspace},
booktitle = {{STACS} 2004, 21st Annual Symposium on Theoretical Aspects of Computer
Science, Montpellier, France, March 25-27, 2004, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2996},
pages = {571--583},
publisher = {Springer},
year = {2004},
url = {https://doi.org/10.1007/978-3-540-24749-4\_50},
doi = {10.1007/978-3-540-24749-4\_50},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/CaiCM04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dam/Cai03,
author = {Jin{-}yi Cai},
title = {A new transference theorem in the geometry of numbers and new bounds
for Ajtai's connection factor},
journal = {Discret. Appl. Math.},
volume = {126},
number = {1},
pages = {9--31},
year = {2003},
url = {https://doi.org/10.1016/S0166-218X(02)00216-0},
doi = {10.1016/S0166-218X(02)00216-0},
timestamp = {Thu, 11 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dam/Cai03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/Cai03,
author = {Jin{-}yi Cai},
title = {Essentially Every Unimodular Matrix Defines an Expander},
journal = {Theory Comput. Syst.},
volume = {36},
number = {2},
pages = {105--135},
year = {2003},
url = {https://doi.org/10.1007/s00224-002-1017-y},
doi = {10.1007/S00224-002-1017-Y},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/Cai03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/CaiB03,
author = {Jin{-}yi Cai and
Eric Bach},
title = {On testing for zero polynomials by a set of points with bounded precision},
journal = {Theor. Comput. Sci.},
volume = {296},
number = {1},
pages = {15--25},
year = {2003},
url = {https://doi.org/10.1016/S0304-3975(02)00429-2},
doi = {10.1016/S0304-3975(02)00429-2},
timestamp = {Wed, 01 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/CaiB03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/CaiW03,
author = {Jin{-}yi Cai and
Osamu Watanabe},
editor = {Tandy J. Warnow and
Binhai Zhu},
title = {On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy:
Positive and Negative Results},
booktitle = {Computing and Combinatorics, 9th Annual International Conference,
{COCOON} 2003, Big Sky, MT, USA, July 25-28, 2003, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2697},
pages = {202--211},
publisher = {Springer},
year = {2003},
url = {https://doi.org/10.1007/3-540-45071-8\_22},
doi = {10.1007/3-540-45071-8\_22},
timestamp = {Tue, 14 May 2019 10:00:35 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/CaiW03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/CaiW03,
author = {Jin{-}yi Cai and
Osamu Watanabe},
editor = {Paritosh K. Pandya and
Jaikumar Radhakrishnan},
title = {Stringent Relativization},
booktitle = {{FST} {TCS} 2003: Foundations of Software Technology and Theoretical
Computer Science, 23rd Conference, Mumbai, India, December 15-17,
2003, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2914},
pages = {408--419},
publisher = {Springer},
year = {2003},
url = {https://doi.org/10.1007/978-3-540-24597-1\_35},
doi = {10.1007/978-3-540-24597-1\_35},
timestamp = {Tue, 14 May 2019 10:00:51 +0200},
biburl = {https://dblp.org/rec/conf/fsttcs/CaiW03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icde/WangDC03,
author = {Yuan Wang and
David J. DeWitt and
Jin{-}yi Cai},
editor = {Umeshwar Dayal and
Krithi Ramamritham and
T. M. Vijayaraman},
title = {X-Diff: An Effective Change Detection Algorithm for {XML} Documents},
booktitle = {Proceedings of the 19th International Conference on Data Engineering,
March 5-8, 2003, Bangalore, India},
pages = {519--530},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/ICDE.2003.1260818},
doi = {10.1109/ICDE.2003.1260818},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icde/WangDC03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/infocom/AdlerCST03,
author = {Micah Adler and
Jin{-}yi Cai and
Jonathan K. Shapiro and
Donald F. Towsley},
title = {Estimation of Congestion Price Using Probabilistic Packet Marking},
booktitle = {Proceedings {IEEE} {INFOCOM} 2003, The 22nd Annual Joint Conference
of the {IEEE} Computer and Communications Societies, San Franciso,
CA, USA, March 30 - April 3, 2003},
pages = {2068--2078},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/INFCOM.2003.1209228},
doi = {10.1109/INFCOM.2003.1209228},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/infocom/AdlerCST03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/CaiCHO03,
author = {Jin{-}yi Cai and
Venkatesan T. Chakaravarthy and
Lane A. Hemaspaandra and
Mitsunori Ogihara},
editor = {Helmut Alt and
Michel Habib},
title = {Competing Provers Yield Improved Karp-Lipton Collapse Results},
booktitle = {{STACS} 2003, 20th Annual Symposium on Theoretical Aspects of Computer
Science, Berlin, Germany, February 27 - March 1, 2003, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2607},
pages = {535--546},
publisher = {Springer},
year = {2003},
url = {https://doi.org/10.1007/3-540-36494-3\_47},
doi = {10.1007/3-540-36494-3\_47},
timestamp = {Thu, 14 Oct 2021 10:38:16 +0200},
biburl = {https://dblp.org/rec/conf/stacs/CaiCHO03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/CaiCPS02,
author = {Jin{-}yi Cai and
Denis Charles and
Aduri Pavan and
Samik Sengupta},
editor = {Oscar H. Ibarra and
Louxin Zhang},
title = {On Higher Arthur-Merlin Classes},
booktitle = {Computing and Combinatorics, 8th Annual International Conference,
{COCOON} 2002, Singapore, August 15-17, 2002, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2387},
pages = {18--27},
publisher = {Springer},
year = {2002},
url = {https://doi.org/10.1007/3-540-45655-4\_4},
doi = {10.1007/3-540-45655-4\_4},
timestamp = {Tue, 14 May 2019 10:00:35 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/CaiCPS02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isaac/Cai02,
author = {Jin{-}yi Cai},
editor = {Prosenjit Bose and
Pat Morin},
title = {On the Minimum Volume of a Perturbed Unit Cube},
booktitle = {Algorithms and Computation, 13th International Symposium, {ISAAC}
2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2518},
pages = {67--78},
publisher = {Springer},
year = {2002},
url = {https://doi.org/10.1007/3-540-36136-7\_7},
doi = {10.1007/3-540-36136-7\_7},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/isaac/Cai02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/CaiB01,
author = {Jin{-}yi Cai and
Eric Bach},
editor = {Jie Wang},
title = {On Testing for Zero Polynomials by a Set of Points with Bounded Precision},
booktitle = {Computing and Combinatorics, 7th Annual International Conference,
{COCOON} 2001, Guilin, China, August 20-23, 2001, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2108},
pages = {473--482},
publisher = {Springer},
year = {2001},
url = {https://doi.org/10.1007/3-540-44679-6\_53},
doi = {10.1007/3-540-44679-6\_53},
timestamp = {Wed, 01 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/cocoon/CaiB01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Cai01,
author = {Jin{-}yi Cai},
title = {On the Average-Case Hardness of {CVP}},
booktitle = {42nd Annual Symposium on Foundations of Computer Science, {FOCS} 2001,
14-17 October 2001, Las Vegas, Nevada, {USA}},
pages = {308--317},
publisher = {{IEEE} Computer Society},
year = {2001},
url = {https://doi.org/10.1109/SFCS.2001.959905},
doi = {10.1109/SFCS.2001.959905},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Cai01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Cai01a,
author = {Jin{-}yi Cai},
title = {S\({}^{\mbox{p}}\)\({}_{\mbox{2}}\) subseteq ZPP\({}^{\mbox{NP}}\)},
booktitle = {42nd Annual Symposium on Foundations of Computer Science, {FOCS} 2001,
14-17 October 2001, Las Vegas, Nevada, {USA}},
pages = {620--629},
publisher = {{IEEE} Computer Society},
year = {2001},
url = {https://doi.org/10.1109/SFCS.2001.959938},
doi = {10.1109/SFCS.2001.959938},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Cai01a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/pods/CaiCKN01,
author = {Jin{-}yi Cai and
Venkatesan T. Chakaravarthy and
Raghav Kaushik and
Jeffrey F. Naughton},
editor = {Peter Buneman},
title = {On the Complexity of Join Predicates},
booktitle = {Proceedings of the Twentieth {ACM} {SIGACT-SIGMOD-SIGART} Symposium
on Principles of Database Systems, May 21-23, 2001, Santa Barbara,
California, {USA}},
publisher = {{ACM}},
year = {2001},
url = {https://doi.org/10.1145/375551.375592},
doi = {10.1145/375551.375592},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/pods/CaiCKN01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR01-001,
author = {Jin{-}yi Cai},
title = {Essentially every unimodular matrix defines an expander},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR01-001}},
year = {2001},
url = {https://eccc.weizmann.ac.il/eccc-reports/2001/TR01-001/index.html},
eprinttype = {ECCC},
eprint = {TR01-001},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR01-001.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR01-030,
author = {Jin{-}yi Cai},
title = {S{\_}2\({}^{\mbox{p}}\) {\textbackslash}subseteq ZPP\({}^{\mbox{NP}}\)},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR01-030}},
year = {2001},
url = {https://eccc.weizmann.ac.il/eccc-reports/2001/TR01-030/index.html},
eprinttype = {ECCC},
eprint = {TR01-030},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR01-030.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/CaiN00,
author = {Jin{-}yi Cai and
Ajay Nerurkar},
title = {A note on the non-NP-hardness of approximate lattice problems under
general Cook reductions},
journal = {Inf. Process. Lett.},
volume = {76},
number = {1-2},
pages = {61--66},
year = {2000},
url = {https://doi.org/10.1016/S0020-0190(00)00123-X},
doi = {10.1016/S0020-0190(00)00123-X},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/CaiN00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiLZ00,
author = {Jin{-}yi Cai and
Richard J. Lipton and
Yechezkel Zalcstein},
title = {The Complexity of the {A} {B} {C} Problem},
journal = {{SIAM} J. Comput.},
volume = {29},
number = {6},
pages = {1878--1888},
year = {2000},
url = {https://doi.org/10.1137/S0097539794276853},
doi = {10.1137/S0097539794276853},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiLZ00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/CaiS00,
author = {Jin{-}yi Cai and
D. Sivakumar},
title = {Resolution of Hartmanis' conjecture for NL-hard sparse sets},
journal = {Theor. Comput. Sci.},
volume = {240},
number = {2},
pages = {257--269},
year = {2000},
url = {https://doi.org/10.1016/S0304-3975(99)00234-0},
doi = {10.1016/S0304-3975(99)00234-0},
timestamp = {Sat, 21 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/CaiS00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ants/Cai00,
author = {Jin{-}yi Cai},
editor = {Wieb Bosma},
title = {The Complexity of Some Lattice Problems},
booktitle = {Algorithmic Number Theory, 4th International Symposium, ANTS-IV, Leiden,
The Netherlands, July 2-7, 2000, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1838},
pages = {1--32},
publisher = {Springer},
year = {2000},
url = {https://doi.org/10.1007/10722028\_1},
doi = {10.1007/10722028\_1},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/ants/Cai00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isaac/Cai00,
author = {Jin{-}yi Cai},
editor = {D. T. Lee and
Shang{-}Hua Teng},
title = {Essentially Every Unimodular Matrix Defines and Expander},
booktitle = {Algorithms and Computation, 11th International Conference, {ISAAC}
2000, Taipei, Taiwan, December 18-20, 2000, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1969},
pages = {2--22},
publisher = {Springer},
year = {2000},
url = {https://doi.org/10.1007/3-540-40996-3\_2},
doi = {10.1007/3-540-40996-3\_2},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/isaac/Cai00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KabanetsC00,
author = {Valentine Kabanets and
Jin{-}yi Cai},
editor = {F. Frances Yao and
Eugene M. Luks},
title = {Circuit minimization problem},
booktitle = {Proceedings of the Thirty-Second Annual {ACM} Symposium on Theory
of Computing, May 21-23, 2000, Portland, OR, {USA}},
pages = {73--79},
publisher = {{ACM}},
year = {2000},
url = {https://doi.org/10.1145/335305.335314},
doi = {10.1145/335305.335314},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/KabanetsC00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/CaiW99,
author = {Jin{-}yi Cai and
C. K. Wong},
title = {Foreword},
journal = {Algorithmica},
volume = {23},
number = {4},
pages = {277},
year = {1999},
url = {https://doi.org/10.1007/PL00009262},
doi = {10.1007/PL00009262},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/CaiW99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/CaiC99,
author = {Jin{-}yi Cai and
Thomas W. Cusick},
title = {A Lattice-Based Public-Key Cryptosystem},
journal = {Inf. Comput.},
volume = {151},
number = {1-2},
pages = {17--31},
year = {1999},
url = {https://doi.org/10.1006/inco.1998.2762},
doi = {10.1006/INCO.1998.2762},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/CaiC99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/Cai99,
author = {Jin{-}yi Cai},
title = {A Classification of the Probabilistic Polynomial Time Hierarchy Under
Fault Tolerant Access to Oracle Classes},
journal = {Inf. Process. Lett.},
volume = {69},
number = {4},
pages = {167--174},
year = {1999},
url = {https://doi.org/10.1016/S0020-0190(99)00011-3},
doi = {10.1016/S0020-0190(99)00011-3},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/Cai99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/CaiS99,
author = {Jin{-}yi Cai and
D. Sivakumar},
title = {Sparse Hard Sets for {P:} Resolution of a Conjecture of Hartmanis},
journal = {J. Comput. Syst. Sci.},
volume = {58},
number = {2},
pages = {280--296},
year = {1999},
url = {https://doi.org/10.1006/jcss.1998.1615},
doi = {10.1006/JCSS.1998.1615},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/CaiS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/CaiN99,
author = {Jin{-}yi Cai and
Ajay Nerurkar},
title = {Approximating the {SVP} to within a Factor (1+1/dim\({}^{\mbox{xi}}\))
Is NP-Hard under Randomized Reductions},
journal = {J. Comput. Syst. Sci.},
volume = {59},
number = {2},
pages = {221--239},
year = {1999},
url = {https://doi.org/10.1006/jcss.1999.1649},
doi = {10.1006/JCSS.1999.1649},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/CaiN99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/CaiHW99,
author = {Jin{-}yi Cai and
Lane A. Hemaspaandra and
Gerd Wechsung},
title = {Robust Reductions},
journal = {Theory Comput. Syst.},
volume = {32},
number = {6},
pages = {625--647},
year = {1999},
url = {https://doi.org/10.1007/s002240000134},
doi = {10.1007/S002240000134},
timestamp = {Mon, 16 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/CaiHW99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiS99,
author = {Jin{-}yi Cai and
Alan L. Selman},
title = {Fine Separation of Average-Time Complexity Classes},
journal = {{SIAM} J. Comput.},
volume = {28},
number = {4},
pages = {1310--1325},
year = {1999},
url = {https://doi.org/10.1137/S0097539796311715},
doi = {10.1137/S0097539796311715},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Cai99,
author = {Jin{-}yi Cai},
title = {Some Recent Progress on the Complexity of Lattice Problems},
booktitle = {Proceedings of the 14th Annual {IEEE} Conference on Computational
Complexity, Atlanta, Georgia, USA, May 4-6, 1999},
pages = {158},
publisher = {{IEEE} Computer Society},
year = {1999},
url = {https://doi.org/10.1109/CCC.1999.766274},
doi = {10.1109/CCC.1999.766274},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Cai99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Cai99a,
author = {Jin{-}yi Cai},
title = {Applications of a New Transference Theorem to Ajtai's Connection Factor},
booktitle = {Proceedings of the 14th Annual {IEEE} Conference on Computational
Complexity, Atlanta, Georgia, USA, May 4-6, 1999},
pages = {205--214},
publisher = {{IEEE} Computer Society},
year = {1999},
url = {https://doi.org/10.1109/CCC.1999.766278},
doi = {10.1109/CCC.1999.766278},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Cai99a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/Cai99,
author = {Jin{-}yi Cai},
editor = {Takao Asano and
Hiroshi Imai and
D. T. Lee and
Shin{-}Ichi Nakano and
Takeshi Tokuyama},
title = {A New Transference Theorem in the Geometry of Numbers},
booktitle = {Computing and Combinatorics, 5th Annual International Conference,
{COCOON} '99, Tokyo, Japan, July 26-28, 1999, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1627},
pages = {113--122},
publisher = {Springer},
year = {1999},
url = {https://doi.org/10.1007/3-540-48686-0\_11},
doi = {10.1007/3-540-48686-0\_11},
timestamp = {Sat, 30 Sep 2023 09:37:25 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/Cai99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/CaiHMNSS99,
author = {Jin{-}yi Cai and
George Havas and
Bernard Mans and
Ajay Nerurkar and
Jean{-}Pierre Seifert and
Igor E. Shparlinski},
editor = {Takao Asano and
Hiroshi Imai and
D. T. Lee and
Shin{-}Ichi Nakano and
Takeshi Tokuyama},
title = {On Routing in Circulant Graphs},
booktitle = {Computing and Combinatorics, 5th Annual International Conference,
{COCOON} '99, Tokyo, Japan, July 26-28, 1999, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1627},
pages = {360--369},
publisher = {Springer},
year = {1999},
url = {https://doi.org/10.1007/3-540-48686-0\_36},
doi = {10.1007/3-540-48686-0\_36},
timestamp = {Sun, 25 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/CaiHMNSS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/CaiPS99,
author = {Jin{-}yi Cai and
Aduri Pavan and
D. Sivakumar},
editor = {Christoph Meinel and
Sophie Tison},
title = {On the Hardness of Permanent},
booktitle = {{STACS} 99, 16th Annual Symposium on Theoretical Aspects of Computer
Science, Trier, Germany, March 4-6, 1999, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1563},
pages = {90--99},
publisher = {Springer},
year = {1999},
url = {https://doi.org/10.1007/3-540-49116-3\_8},
doi = {10.1007/3-540-49116-3\_8},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/CaiPS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CaiNS99,
author = {Jin{-}yi Cai and
Ajay Nerurkar and
D. Sivakumar},
editor = {Jeffrey Scott Vitter and
Lawrence L. Larmore and
Frank Thomson Leighton},
title = {Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial
Time},
booktitle = {Proceedings of the Thirty-First Annual {ACM} Symposium on Theory of
Computing, May 1-4, 1999, Atlanta, Georgia, {USA}},
pages = {726--735},
publisher = {{ACM}},
year = {1999},
url = {https://doi.org/10.1145/301250.301444},
doi = {10.1145/301250.301444},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CaiNS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/cs-CC-9906033,
author = {Jin{-}yi Cai and
Lane A. Hemaspaandra and
Gerd Wechsung},
title = {Robust Reductions},
journal = {CoRR},
volume = {cs.CC/9906033},
year = {1999},
url = {https://arxiv.org/abs/cs/9906033},
timestamp = {Fri, 10 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/cs-CC-9906033.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR99-006,
author = {Jin{-}yi Cai},
title = {Some Recent Progress on the Complexity of Lattice Problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR99-006}},
year = {1999},
url = {https://eccc.weizmann.ac.il/eccc-reports/1999/TR99-006/index.html},
eprinttype = {ECCC},
eprint = {TR99-006},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR99-006.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR99-045,
author = {Valentine Kabanets and
Jin{-}yi Cai},
title = {Circuit Minimization Problem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR99-045}},
year = {1999},
url = {https://eccc.weizmann.ac.il/eccc-reports/1999/TR99-045/index.html},
eprinttype = {ECCC},
eprint = {TR99-045},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR99-045.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jc/CaiCZ98,
author = {Jin{-}yi Cai and
Pu Cai and
Yixin Zhu},
title = {On {A} Scheduling Problem of Time Deteriorating Jobs},
journal = {J. Complex.},
volume = {14},
number = {2},
pages = {190--209},
year = {1998},
url = {https://doi.org/10.1006/jcom.1998.0473},
doi = {10.1006/JCOM.1998.0473},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jc/CaiCZ98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jco/CaiCN98,
author = {Pu Cai and
Jin{-}yi Cai and
Ashish V. Naik},
title = {Efficient Algorithms for a Scheduling Problem and its Applications
to Illicit Drug Market Crackdowns},
journal = {J. Comb. Optim.},
volume = {1},
number = {4},
pages = {367--376},
year = {1998},
url = {https://doi.org/10.1023/A:1009738610804},
doi = {10.1023/A:1009738610804},
timestamp = {Thu, 18 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jco/CaiCN98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/Cai98,
author = {Jin{-}yi Cai},
title = {Frobenius's Degree Formula and Toda's Polynomials},
journal = {Theory Comput. Syst.},
volume = {31},
number = {1},
pages = {67--75},
year = {1998},
url = {https://doi.org/10.1007/s002240000078},
doi = {10.1007/S002240000078},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/Cai98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/Cai98,
author = {Jin{-}yi Cai},
title = {A Relation of Primal-Dual Lattices and the Complexity of Shortest
Lattice Vector Problem},
journal = {Theor. Comput. Sci.},
volume = {207},
number = {1},
pages = {105--116},
year = {1998},
url = {https://doi.org/10.1016/S0304-3975(98)00058-9},
doi = {10.1016/S0304-3975(98)00058-9},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/Cai98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiN98,
author = {Jin{-}yi Cai and
Ajay Nerurkar},
title = {Approximating the {SVP} to within a Factor is NP-Hard under Randomized
Reductions},
booktitle = {Proceedings of the 13th Annual {IEEE} Conference on Computational
Complexity, Buffalo, New York, USA, June 15-18, 1998},
pages = {46},
publisher = {{IEEE} Computer Society},
year = {1998},
url = {https://doi.org/10.1109/CCC.1998.694590},
doi = {10.1109/CCC.1998.694590},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/CaiN98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/CaiHW98,
author = {Jin{-}yi Cai and
Lane A. Hemaspaandra and
Gerd Wechsung},
editor = {Wen{-}Lian Hsu and
Ming{-}Yang Kao},
title = {Robust Reductions},
booktitle = {Computing and Combinatorics, 4th Annual International Conference,
{COCOON} '98, Taipei, Taiwan, R.o.C., August 12-14, 1998, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1449},
pages = {174--183},
publisher = {Springer},
year = {1998},
url = {https://doi.org/10.1007/3-540-68535-9\_21},
doi = {10.1007/3-540-68535-9\_21},
timestamp = {Mon, 16 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/CaiHW98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sacrypt/CaiC98,
author = {Jin{-}yi Cai and
Thomas W. Cusick},
editor = {Stafford E. Tavares and
Henk Meijer},
title = {A Lattice-Based Public-Key Cryptosystem},
booktitle = {Selected Areas in Cryptography '98, SAC'98, Kingston, Ontario, Canada,
August 17-18, 1998, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1556},
pages = {219--233},
publisher = {Springer},
year = {1998},
url = {https://doi.org/10.1007/3-540-48892-8\_18},
doi = {10.1007/3-540-48892-8\_18},
timestamp = {Tue, 14 May 2019 10:00:38 +0200},
biburl = {https://dblp.org/rec/conf/sacrypt/CaiC98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR98-005,
author = {Jin{-}yi Cai},
title = {A new transference theorem and applications to Ajtai's connection
factor},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR98-005}},
year = {1998},
url = {https://eccc.weizmann.ac.il/eccc-reports/1998/TR98-005/index.html},
eprinttype = {ECCC},
eprint = {TR98-005},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR98-005.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/CaiS97,
author = {Jin{-}yi Cai and
D. Sivakumar},
editor = {Tao Jiang and
D. T. Lee},
title = {Resolution of Hartmanis' Conjecture for NL-Hard Sparse Sets},
booktitle = {Computing and Combinatorics, Third Annual International Conference,
{COCOON} '97, Shanghai, China, August 20-22, 1997, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1276},
pages = {62--71},
publisher = {Springer},
year = {1997},
url = {https://doi.org/10.1007/BFb0045073},
doi = {10.1007/BFB0045073},
timestamp = {Tue, 14 May 2019 10:00:35 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/CaiS97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/CaiC97,
author = {Pu Cai and
Jin{-}yi Cai},
editor = {Tao Jiang and
D. T. Lee},
title = {On the 100{\%} Rule of Sensivity Analzsis in Linear Programming},
booktitle = {Computing and Combinatorics, Third Annual International Conference,
{COCOON} '97, Shanghai, China, August 20-22, 1997, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1276},
pages = {460--469},
publisher = {Springer},
year = {1997},
url = {https://doi.org/10.1007/BFb0045113},
doi = {10.1007/BFB0045113},
timestamp = {Mon, 22 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/CaiC97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiN97,
author = {Jin{-}yi Cai and
Ajay Nerurkar},
title = {An Improved Worst-Case to Average-Case Connection for Lattice Problems},
booktitle = {38th Annual Symposium on Foundations of Computer Science, {FOCS} '97,
Miami Beach, Florida, USA, October 19-22, 1997},
pages = {468--477},
publisher = {{IEEE} Computer Society},
year = {1997},
url = {https://doi.org/10.1109/SFCS.1997.646135},
doi = {10.1109/SFCS.1997.646135},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CaiN97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiSS97,
author = {Jin{-}yi Cai and
D. Sivakumar and
Martin Strauss},
title = {Constant Depth Circuits and the Lutz Hypothesis},
booktitle = {38th Annual Symposium on Foundations of Computer Science, {FOCS} '97,
Miami Beach, Florida, USA, October 19-22, 1997},
pages = {595--604},
publisher = {{IEEE} Computer Society},
year = {1997},
url = {https://doi.org/10.1109/SFCS.1997.646149},
doi = {10.1109/SFCS.1997.646149},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CaiSS97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR97-059,
author = {Jin{-}yi Cai and
Ajay Nerurkar},
title = {Approximating the {SVP} to within a factor {(1} + 1/dim\({}^{\mbox{epsilon}}\))
is NP-hard under randomized reductions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR97-059}},
year = {1997},
url = {https://eccc.weizmann.ac.il/eccc-reports/1997/TR97-059/index.html},
eprinttype = {ECCC},
eprint = {TR97-059},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR97-059.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/CaiGT96,
author = {Jin{-}yi Cai and
Frederic Green and
Thomas Thierauf},
title = {On the Correlation of Symmetric Functions},
journal = {Math. Syst. Theory},
volume = {29},
number = {3},
pages = {245--258},
year = {1996},
url = {https://doi.org/10.1007/BF01201278},
doi = {10.1007/BF01201278},
timestamp = {Sun, 17 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/CaiGT96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/CaiL96,
author = {Jin{-}yi Cai and
Zicheng Liu},
title = {The Bounded Membership Problem of the Monoid SL{\_}2(N)},
journal = {Math. Syst. Theory},
volume = {29},
number = {6},
pages = {573--587},
year = {1996},
url = {https://doi.org/10.1007/bf01301965},
doi = {10.1007/BF01301965},
timestamp = {Fri, 10 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/CaiL96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BabaiBCIL96,
author = {L{\'{a}}szl{\'{o}} Babai and
Robert Beals and
Jin{-}yi Cai and
G{\'{a}}bor Ivanyos and
Eugene M. Luks},
editor = {{\'{E}}va Tardos},
title = {Multiplicative Equations over Commuting Matrices},
booktitle = {Proceedings of the Seventh Annual {ACM-SIAM} Symposium on Discrete
Algorithms, 28-30 January 1996, Atlanta, Georgia, {USA}},
pages = {498--507},
publisher = {{ACM/SIAM}},
year = {1996},
url = {http://dl.acm.org/citation.cfm?id=313852.314109},
timestamp = {Thu, 05 Jul 2018 07:29:31 +0200},
biburl = {https://dblp.org/rec/conf/soda/BabaiBCIL96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/CaiNS96,
author = {Jin{-}yi Cai and
Ashish V. Naik and
D. Sivakumar},
editor = {Claude Puech and
R{\"{u}}diger Reischuk},
title = {On the Existence of Hard Sparse Sets under Weak Reductions},
booktitle = {{STACS} 96, 13th Annual Symposium on Theoretical Aspects of Computer
Science, Grenoble, France, February 22-24, 1996, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1046},
pages = {307--318},
publisher = {Springer},
year = {1996},
url = {https://doi.org/10.1007/3-540-60922-9\_26},
doi = {10.1007/3-540-60922-9\_26},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/CaiNS96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/CaiS96,
author = {Jin{-}yi Cai and
Alan L. Selman},
editor = {Claude Puech and
R{\"{u}}diger Reischuk},
title = {Fine Separation of Average Time Complexity Classes},
booktitle = {{STACS} 96, 13th Annual Symposium on Theoretical Aspects of Computer
Science, Grenoble, France, February 22-24, 1996, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1046},
pages = {331--343},
publisher = {Springer},
year = {1996},
url = {https://doi.org/10.1007/3-540-60922-9\_28},
doi = {10.1007/3-540-60922-9\_28},
timestamp = {Mon, 22 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stacs/CaiS96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/coco/1996,
editor = {Steven Homer and
Jin{-}Yi Cai},
title = {Proceedings of the Eleveth Annual {IEEE} Conference on Computational
Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996},
publisher = {{IEEE} Computer Society},
year = {1996},
url = {https://ieeexplore.ieee.org/xpl/conhome/3765/proceeding},
isbn = {0-8186-7386-9},
timestamp = {Thu, 02 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/1996.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/cocoon/1996,
editor = {Jin{-}yi Cai and
C. K. Wong},
title = {Computing and Combinatorics, Second Annual International Conference,
{COCOON} '96, Hong Kong, June 17-19, 1996, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1090},
publisher = {Springer},
year = {1996},
url = {https://doi.org/10.1007/3-540-61332-3},
doi = {10.1007/3-540-61332-3},
isbn = {3-540-61332-3},
timestamp = {Tue, 14 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/1996.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/CaiC95,
author = {Jin{-}yi Cai and
Suresh Chari},
title = {On the Impossibility of Amplifying the Independence of Random Variables},
journal = {Random Struct. Algorithms},
volume = {7},
number = {4},
pages = {301--310},
year = {1995},
url = {https://doi.org/10.1002/rsa.3240070404},
doi = {10.1002/RSA.3240070404},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/rsa/CaiC95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ReganSC95,
author = {Kenneth W. Regan and
D. Sivakumar and
Jin{-}yi Cai},
title = {Pseudorandom Generators, Measure Theory, and Natural Proofs},
booktitle = {36th Annual Symposium on Foundations of Computer Science, Milwaukee,
Wisconsin, USA, 23-25 October 1995},
pages = {26--35},
publisher = {{IEEE} Computer Society},
year = {1995},
url = {https://doi.org/10.1109/SFCS.1995.492459},
doi = {10.1109/SFCS.1995.492459},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ReganSC95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiS95,
author = {Jin{-}yi Cai and
D. Sivakumar},
title = {The Resolution of a Hartmanis Conjecture},
booktitle = {36th Annual Symposium on Foundations of Computer Science, Milwaukee,
Wisconsin, USA, 23-25 October 1995},
pages = {362--371},
publisher = {{IEEE} Computer Society},
year = {1995},
url = {https://doi.org/10.1109/SFCS.1995.492492},
doi = {10.1109/SFCS.1995.492492},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CaiS95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/CaiLLORS95,
author = {Jin{-}yi Cai and
Richard J. Lipton and
Luc Longpr{\'{e}} and
Mitsunori Ogihara and
Kenneth W. Regan and
D. Sivakumar},
editor = {Ernst W. Mayr and
Claude Puech},
title = {Communication Complexity of Key Agreement on Small Ranges},
booktitle = {{STACS} 95, 12th Annual Symposium on Theoretical Aspects of Computer
Science, Munich, Germany, March 2-4, 1995, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {900},
pages = {38--49},
publisher = {Springer},
year = {1995},
url = {https://doi.org/10.1007/3-540-59042-0\_60},
doi = {10.1007/3-540-59042-0\_60},
timestamp = {Sat, 07 Sep 2019 11:59:26 +0200},
biburl = {https://dblp.org/rec/conf/stacs/CaiLLORS95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR95-006,
author = {Kenneth W. Regan and
D. Sivakumar and
Jin{-}yi Cai},
title = {Pseudorandom Generators, Measure Theory, and Natural Proofs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR95-006}},
year = {1995},
url = {https://eccc.weizmann.ac.il/eccc-reports/1995/TR95-006/index.html},
eprinttype = {ECCC},
eprint = {TR95-006},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR95-006.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR95-019,
author = {Jin{-}yi Cai and
Alan L. Selman},
title = {Average Time Complexity Classes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR95-019}},
year = {1995},
url = {https://eccc.weizmann.ac.il/eccc-reports/1995/TR95-019/index.html},
eprinttype = {ECCC},
eprint = {TR95-019},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR95-019.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ijfcs/Cai94,
author = {Jin{-}yi Cai},
title = {Computing Jordan Normal Forms Exactly for Commuting Matrices in Polynomial
Time},
journal = {Int. J. Found. Comput. Sci.},
volume = {5},
number = {3/4},
pages = {293--302},
year = {1994},
url = {https://doi.org/10.1142/S0129054194000165},
doi = {10.1142/S0129054194000165},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ijfcs/Cai94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/CaiCL94,
author = {Jin{-}yi Cai and
Anne Condon and
Richard J. Lipton},
title = {{PSPACE} Is Provable by Two Provers in One Round},
journal = {J. Comput. Syst. Sci.},
volume = {48},
number = {1},
pages = {183--193},
year = {1994},
url = {https://doi.org/10.1016/S0022-0000(05)80026-1},
doi = {10.1016/S0022-0000(05)80026-1},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/CaiCL94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/CaiH94,
author = {Jin{-}yi Cai and
Juris Hartmanis},
title = {On Hausdorff and Topological Dimensions of the Kolmogorov Complexity
of the Real Line},
journal = {J. Comput. Syst. Sci.},
volume = {49},
number = {3},
pages = {605--619},
year = {1994},
url = {https://doi.org/10.1016/S0022-0000(05)80073-X},
doi = {10.1016/S0022-0000(05)80073-X},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/CaiH94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiL94,
author = {Jin{-}yi Cai and
Richard J. Lipton},
title = {Subquadratic Simulations of Balanced Formulae by Branching Programs},
journal = {{SIAM} J. Comput.},
volume = {23},
number = {3},
pages = {563--572},
year = {1994},
url = {https://doi.org/10.1137/S0097539790181336},
doi = {10.1137/S0097539790181336},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiL94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiLZ94,
author = {Jin{-}yi Cai and
Richard J. Lipton and
Yechezkel Zalcstein},
title = {The Complexity of the Membership Problem for 2-generated Commutative
Semigroups of Rational Matrices},
booktitle = {35th Annual Symposium on Foundations of Computer Science, Santa Fe,
New Mexico, USA, 20-22 November 1994},
pages = {135--142},
publisher = {{IEEE} Computer Society},
year = {1994},
url = {https://doi.org/10.1109/SFCS.1994.365699},
doi = {10.1109/SFCS.1994.365699},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CaiLZ94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiFKL94,
author = {Jin{-}yi Cai and
Wolfgang H. J. Fuchs and
Dexter Kozen and
Zicheng Liu},
title = {Efficient Average-Case Algorithms for the Modular Group},
booktitle = {35th Annual Symposium on Foundations of Computer Science, Santa Fe,
New Mexico, USA, 20-22 November 1994},
pages = {143--152},
publisher = {{IEEE} Computer Society},
year = {1994},
url = {https://doi.org/10.1109/SFCS.1994.365698},
doi = {10.1109/SFCS.1994.365698},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CaiFKL94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isaac/CaiH94,
author = {Jin{-}yi Cai and
Michael D. Hirsch},
editor = {Ding{-}Zhu Du and
Xiang{-}Sun Zhang},
title = {Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic
Geometry},
booktitle = {Algorithms and Computation, 5th International Symposium, {ISAAC} '94,
Beijing, P. R. China, August 25-27, 1994, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {834},
pages = {172--180},
publisher = {Springer},
year = {1994},
url = {https://doi.org/10.1007/3-540-58325-4\_179},
doi = {10.1007/3-540-58325-4\_179},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/isaac/CaiH94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ArC94,
author = {Sigal Ar and
Jin{-}yi Cai},
editor = {Daniel Dominic Sleator},
title = {Reliable Benchmarks Using Numerical Instability},
booktitle = {Proceedings of the Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms.
23-25 January 1994, Arlington, Virginia, {USA}},
pages = {34--43},
publisher = {{ACM/SIAM}},
year = {1994},
url = {http://dl.acm.org/citation.cfm?id=314464.314476},
timestamp = {Thu, 05 Jul 2018 07:29:19 +0200},
biburl = {https://dblp.org/rec/conf/soda/ArC94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR94-016,
author = {Jin{-}yi Cai and
Wolfgang H. J. Fuchs and
Dexter Kozen and
Zicheng Liu},
title = {Efficient Average-Case Algorithms for the Modular Group},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR94-016}},
year = {1994},
url = {https://eccc.weizmann.ac.il/eccc-reports/1994/TR94-016/index.html},
eprinttype = {ECCC},
eprint = {TR94-016},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR94-016.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/BhattC93,
author = {Sandeep N. Bhatt and
Jin{-}yi Cai},
title = {Taking Random Walks to Grow Trees in Hypercubes},
journal = {J. {ACM}},
volume = {40},
number = {3},
pages = {741--764},
year = {1993},
url = {https://doi.org/10.1145/174130.174144},
doi = {10.1145/174130.174144},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/BhattC93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiLSY93,
author = {Jin{-}yi Cai and
Richard J. Lipton and
Robert Sedgewick and
Andrew Chi{-}Chih Yao},
title = {Towards Uncheatable benchmarks},
booktitle = {Proceedings of the Eigth Annual Structure in Complexity Theory Conference,
San Diego, CA, USA, May 18-21, 1993},
pages = {2--11},
publisher = {{IEEE} Computer Society},
year = {1993},
url = {https://doi.org/10.1109/SCT.1993.336546},
doi = {10.1109/SCT.1993.336546},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/CaiLSY93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/dimacs/dimacs13,
editor = {Jin{-}Yi Cai},
title = {Advances In Computational Complexity Theory, Proceedings of a {DIMACS}
Workshop, New Jersey, USA, December 3-7, 1990},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {13},
publisher = {{DIMACS/AMS}},
year = {1993},
url = {https://doi.org/10.1090/dimacs/013},
doi = {10.1090/DIMACS/013},
isbn = {978-0-8218-6597-2},
timestamp = {Mon, 22 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/dimacs13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/combinatorica/CaiFI92,
author = {Jin{-}yi Cai and
Martin F{\"{u}}rer and
Neil Immerman},
title = {An optimal lower bound on the number of variables for graph identification},
journal = {Comb.},
volume = {12},
number = {4},
pages = {389--410},
year = {1992},
url = {https://doi.org/10.1007/BF01305232},
doi = {10.1007/BF01305232},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/combinatorica/CaiFI92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/CaiCL92,
author = {Jin{-}yi Cai and
Anne Condon and
Richard J. Lipton},
title = {On Games of Incomplete Information},
journal = {Theor. Comput. Sci.},
volume = {103},
number = {1},
pages = {25--38},
year = {1992},
url = {https://doi.org/10.1016/0304-3975(92)90085-T},
doi = {10.1016/0304-3975(92)90085-T},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/CaiCL92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/CaiHV92,
author = {Jin{-}yi Cai and
Lane A. Hemachandra and
Jozef Vyskoc},
editor = {Klaus Ambos{-}Spies and
Steven Homer and
Uwe Sch{\"{o}}ning},
title = {Promise Problems and Guarded Access to Unambiguous Computation},
booktitle = {Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8,
1992},
pages = {101--146},
publisher = {Cambridge University Press},
year = {1992},
timestamp = {Mon, 15 Jul 2002 11:29:49 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/CaiHV92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/CaiHV92,
author = {Jin{-}yi Cai and
Lane A. Hemachandra and
Jozef Vyskoc},
editor = {Ivan M. Havel and
V{\'{a}}clav Koubek},
title = {Promise Problems and Access to Unambiguous Computation},
booktitle = {Mathematical Foundations of Computer Science 1992, 17th International
Symposium, MFCS'92, Prague, Czechoslovakia, August 24-28, 1992, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {629},
pages = {162--171},
publisher = {Springer},
year = {1992},
url = {https://doi.org/10.1007/3-540-55808-X\_14},
doi = {10.1007/3-540-55808-X\_14},
timestamp = {Mon, 16 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/CaiHV92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Cai92,
author = {Jin{-}yi Cai},
editor = {S. Rao Kosaraju and
Mike Fellows and
Avi Wigderson and
John A. Ellis},
title = {Parallel Computation Over Hyperbolic Groups},
booktitle = {Proceedings of the 24th Annual {ACM} Symposium on Theory of Computing,
May 4-6, 1992, Victoria, British Columbia, Canada},
pages = {106--115},
publisher = {{ACM}},
year = {1992},
url = {https://doi.org/10.1145/129712.129723},
doi = {10.1145/129712.129723},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Cai92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ijfcs/CaiF91,
author = {Jin{-}yi Cai and
Merrick L. Furst},
title = {{PSPACE} Survives Constant-Width Bottlenecks},
journal = {Int. J. Found. Comput. Sci.},
volume = {2},
number = {1},
pages = {67--76},
year = {1991},
url = {https://doi.org/10.1142/S0129054191000054},
doi = {10.1142/S0129054191000054},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ijfcs/CaiF91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/CaiH91,
author = {Jin{-}yi Cai and
Lane A. Hemachandra},
title = {A Note on Enumarative Counting},
journal = {Inf. Process. Lett.},
volume = {38},
number = {4},
pages = {215--219},
year = {1991},
url = {https://doi.org/10.1016/0020-0190(91)90103-O},
doi = {10.1016/0020-0190(91)90103-O},
timestamp = {Mon, 16 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/CaiH91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiCL91,
author = {Jin{-}yi Cai and
Anne Condon and
Richard J. Lipton},
title = {{PSPACE} Is Provable By Two Provers In One Round},
booktitle = {Proceedings of the Sixth Annual Structure in Complexity Theory Conference,
Chicago, Illinois, USA, June 30 - July 3, 1991},
pages = {110--115},
publisher = {{IEEE} Computer Society},
year = {1991},
url = {https://doi.org/10.1109/SCT.1991.160250},
doi = {10.1109/SCT.1991.160250},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/CaiCL91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fct/Cai91,
author = {Jin{-}yi Cai},
editor = {Lothar Budach},
title = {Computations Over Infinite Groups},
booktitle = {Fundamentals of Computation Theory, 8th International Symposium, {FCT}
'91, Gosen, Germany, September 9-13, 1991, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {529},
pages = {22--32},
publisher = {Springer},
year = {1991},
url = {https://doi.org/10.1007/3-540-54458-5\_46},
doi = {10.1007/3-540-54458-5\_46},
timestamp = {Tue, 14 May 2019 10:00:53 +0200},
biburl = {https://dblp.org/rec/conf/fct/Cai91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/Cai90,
author = {Jin{-}yi Cai},
title = {A Note on the Determinant and Permanent Problem},
journal = {Inf. Comput.},
volume = {84},
number = {1},
pages = {119--127},
year = {1990},
url = {https://doi.org/10.1016/0890-5401(90)90036-H},
doi = {10.1016/0890-5401(90)90036-H},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/Cai90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/Cai90,
author = {Jin{-}yi Cai},
title = {Lower Bounds for Constant-Depth Circuits in the Presence of Help Bits},
journal = {Inf. Process. Lett.},
volume = {36},
number = {2},
pages = {79--83},
year = {1990},
url = {https://doi.org/10.1016/0020-0190(90)90101-3},
doi = {10.1016/0020-0190(90)90101-3},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/Cai90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/CaiH90,
author = {Jin{-}yi Cai and
Lane A. Hemachandra},
title = {On the Power of Parity Polynomial Time},
journal = {Math. Syst. Theory},
volume = {23},
number = {2},
pages = {95--106},
year = {1990},
url = {https://doi.org/10.1007/BF02090768},
doi = {10.1007/BF02090768},
timestamp = {Sun, 17 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/CaiH90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiCL90,
author = {Jin{-}yi Cai and
Anne Condon and
Richard J. Lipton},
title = {On Bounded Round Multi-Prover Interactive Proof Systems},
booktitle = {Proceedings: Fifth Annual Structure in Complexity Theory Conference,
Universitat Polit{\`{e}}cnica de Catalunya, Barcelona, Spain, July
8-11, 1990},
pages = {45--54},
publisher = {{IEEE} Computer Society},
year = {1990},
url = {https://doi.org/10.1109/SCT.1990.113953},
doi = {10.1109/SCT.1990.113953},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/CaiCL90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/CaiCL90,
author = {Jin{-}yi Cai and
Anne Condon and
Richard J. Lipton},
editor = {Christian Choffrut and
Thomas Lengauer},
title = {Playing Games of Incomplete Information},
booktitle = {{STACS} 90, 7th Annual Symposium on Theoretical Aspects of Computer
Science, Rouen, France, February 22-24, 1990, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {415},
pages = {58--69},
publisher = {Springer},
year = {1990},
url = {https://doi.org/10.1007/3-540-52282-4\_32},
doi = {10.1007/3-540-52282-4\_32},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/CaiCL90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/CaiH89,
author = {Jin{-}yi Cai and
Lane A. Hemachandra},
title = {Enumerative Counting Is Hard},
journal = {Inf. Comput.},
volume = {82},
number = {1},
pages = {34--44},
year = {1989},
url = {https://doi.org/10.1016/0890-5401(89)90063-1},
doi = {10.1016/0890-5401(89)90063-1},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/CaiH89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/Cai89,
author = {Jin{-}yi Cai},
title = {With Probability One, a Random Oracle Separates {PSPACE} from the
Polynomial-Time Hierarchy},
journal = {J. Comput. Syst. Sci.},
volume = {38},
number = {1},
pages = {68--85},
year = {1989},
url = {https://doi.org/10.1016/0022-0000(89)90033-0},
doi = {10.1016/0022-0000(89)90033-0},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/Cai89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiGHHSWW89,
author = {Jin{-}yi Cai and
Thomas Gundermann and
Juris Hartmanis and
Lane A. Hemachandra and
Vivian Sewelson and
Klaus W. Wagner and
Gerd Wechsung},
title = {The Boolean Hierarchy {II:} Applications},
journal = {{SIAM} J. Comput.},
volume = {18},
number = {1},
pages = {95--111},
year = {1989},
url = {https://doi.org/10.1137/0218007},
doi = {10.1137/0218007},
timestamp = {Mon, 16 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiGHHSWW89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiH89,
author = {Jin{-}yi Cai and
Juris Hartmanis},
title = {The Complexity Of The Real Line Is {A} Fractal},
booktitle = {Proceedings: Fourth Annual Structure in Complexity Theory Conference,
University of Oregon, Eugene, Oregon, USA, June 19-22, 1989},
pages = {138--146},
publisher = {{IEEE} Computer Society},
year = {1989},
url = {https://doi.org/10.1109/SCT.1989.41820},
doi = {10.1109/SCT.1989.41820},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/CaiH89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Cai89,
author = {Jin{-}yi Cai},
title = {Lower Bounds for Constant Depth Circuits in the Presence of Help Bits},
booktitle = {30th Annual Symposium on Foundations of Computer Science, Research
Triangle Park, North Carolina, USA, 30 October - 1 November 1989},
pages = {532--537},
publisher = {{IEEE} Computer Society},
year = {1989},
url = {https://doi.org/10.1109/SFCS.1989.63530},
doi = {10.1109/SFCS.1989.63530},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Cai89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiL89,
author = {Jin{-}yi Cai and
Richard J. Lipton},
title = {Subquadratic Simulations of Circuits by Branching Programs},
booktitle = {30th Annual Symposium on Foundations of Computer Science, Research
Triangle Park, North Carolina, USA, 30 October - 1 November 1989},
pages = {568--573},
publisher = {{IEEE} Computer Society},
year = {1989},
url = {https://doi.org/10.1109/SFCS.1989.63536},
doi = {10.1109/SFCS.1989.63536},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CaiL89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiFI89,
author = {Jin{-}yi Cai and
Martin F{\"{u}}rer and
Neil Immerman},
title = {An Optimal Lower Bound on the Number of Variables for Graph Identification},
booktitle = {30th Annual Symposium on Foundations of Computer Science, Research
Triangle Park, North Carolina, USA, 30 October - 1 November 1989},
pages = {612--617},
publisher = {{IEEE} Computer Society},
year = {1989},
url = {https://doi.org/10.1109/SFCS.1989.63543},
doi = {10.1109/SFCS.1989.63543},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CaiFI89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/CaiH89,
author = {Jin{-}yi Cai and
Lane A. Hemachandra},
editor = {Burkhard Monien and
Robert Cori},
title = {On the Power of Parity Polynomial Time},
booktitle = {{STACS} 89, 6th Annual Symposium on Theoretical Aspects of Computer
Science, Paderborn, FRG, February 16-18, 1989, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {349},
pages = {229--239},
publisher = {Springer},
year = {1989},
url = {https://doi.org/10.1007/BFb0028987},
doi = {10.1007/BFB0028987},
timestamp = {Mon, 16 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stacs/CaiH89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiGHHSWW88,
author = {Jin{-}yi Cai and
Thomas Gundermann and
Juris Hartmanis and
Lane A. Hemachandra and
Vivian Sewelson and
Klaus W. Wagner and
Gerd Wechsung},
title = {The Boolean Hierarchy {I:} Structural Properties},
journal = {{SIAM} J. Comput.},
volume = {17},
number = {6},
pages = {1232--1252},
year = {1988},
url = {https://doi.org/10.1137/0217078},
doi = {10.1137/0217078},
timestamp = {Mon, 16 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiGHHSWW88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiH88,
author = {Jin{-}Yi Cai and
Lane A. Hemachandra},
title = {Enumerative counting is hard},
booktitle = {Proceedings: Third Annual Structure in Complexity Theory Conference,
Georgetown University, Washington, D. C., USA, June 14-17, 1988},
pages = {194--203},
publisher = {{IEEE} Computer Society},
year = {1988},
url = {https://doi.org/10.1109/SCT.1988.5279},
doi = {10.1109/SCT.1988.5279},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/CaiH88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BhattC88,
author = {Sandeep N. Bhatt and
Jin{-}yi Cai},
title = {Take a Walk, Grow a Tree (Preliminary Version)},
booktitle = {29th Annual Symposium on Foundations of Computer Science, White Plains,
New York, USA, 24-26 October 1988},
pages = {469--478},
publisher = {{IEEE} Computer Society},
year = {1988},
url = {https://doi.org/10.1109/SFCS.1988.21963},
doi = {10.1109/SFCS.1988.21963},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BhattC88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiM87,
author = {Jin{-}yi Cai and
Gabriele E. Meyer},
title = {Graph Minimal Uncolorability is D{\^{}}P-Complete},
journal = {{SIAM} J. Comput.},
volume = {16},
number = {2},
pages = {259--277},
year = {1987},
url = {https://doi.org/10.1137/0216022},
doi = {10.1137/0216022},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiM87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiF87,
author = {Jin{-}Yi Cai and
Merrick L. Furst},
title = {{PSPACE} survives three-bit bottlenecks},
booktitle = {Proceedings of the Second Annual Conference on Structure in Complexity
Theory, Cornell University, Ithaca, New York, USA, June 16-19, 1987},
pages = {94--102},
publisher = {{IEEE} Computer Society},
year = {1987},
url = {https://ieeexplore.ieee.org/document/10319258},
timestamp = {Tue, 21 Nov 2023 11:59:25 +0100},
biburl = {https://dblp.org/rec/conf/coco/CaiF87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/CaiM87,
author = {Jin{-}yi Cai and
Gabriele E. Meyer},
editor = {Thomas Ottmann},
title = {On the Complexity of Graph Critical Uncolorability},
booktitle = {Automata, Languages and Programming, 14th International Colloquium,
ICALP87, Karlsruhe, Germany, July 13-17, 1987, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {267},
pages = {394--403},
publisher = {Springer},
year = {1987},
url = {https://doi.org/10.1007/3-540-18088-5\_34},
doi = {10.1007/3-540-18088-5\_34},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/CaiM87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/Cai87,
author = {Jin{-}yi Cai},
editor = {Franz{-}Josef Brandenburg and
Guy Vidal{-}Naquet and
Martin Wirsing},
title = {Probability One Separation of the Boolean Hierarchy},
booktitle = {{STACS} 87, 4th Annual Symposium on Theoretical Aspects of Computer
Science, Passau, Germany, February 19-21, 1987, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {247},
pages = {148--158},
publisher = {Springer},
year = {1987},
url = {https://doi.org/10.1007/BFb0039602},
doi = {10.1007/BFB0039602},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/Cai87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@phdthesis{DBLP:phd/us/Cai86,
author = {Jin{-}Yi Cai},
title = {On Some Most Probable Separations of Complexity Classes},
school = {Cornell University, {USA}},
year = {1986},
timestamp = {Mon, 28 Mar 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/phd/us/Cai86.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Cai86,
author = {Jin{-}yi Cai},
editor = {Alan L. Selman},
title = {With Probability One, {A} Random Oracle Separates {PSPACE} from the
Polynomial- Time Hierarchy},
booktitle = {Structure in Complexity Theory, Proceedings of the Conference hold
at the University of California, Berkeley, California, USA, June 2-5,
1986},
series = {Lecture Notes in Computer Science},
volume = {223},
pages = {104--104},
publisher = {Springer},
year = {1986},
url = {https://doi.org/10.1007/3-540-16486-3\_92},
doi = {10.1007/3-540-16486-3\_92},
timestamp = {Thu, 02 Feb 2023 13:27:01 +0100},
biburl = {https://dblp.org/rec/conf/coco/Cai86.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiH86,
author = {Jin{-}yi Cai and
Lane A. Hemachandra},
editor = {Alan L. Selman},
title = {The Boolean Hierarchy: Hardware over {NP}},
booktitle = {Structure in Complexity Theory, Proceedings of the Conference hold
at the University of California, Berkeley, California, USA, June 2-5,
1986},
series = {Lecture Notes in Computer Science},
volume = {223},
pages = {105--124},
publisher = {Springer},
year = {1986},
url = {https://doi.org/10.1007/3-540-16486-3\_93},
doi = {10.1007/3-540-16486-3\_93},
timestamp = {Thu, 02 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/CaiH86.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Cai86,
author = {Jin{-}yi Cai},
editor = {Juris Hartmanis},
title = {With Probability One, {A} Random Oracle Separates {PSPACE} from the
Polynomial-Time Hierarchy},
booktitle = {Proceedings of the 18th Annual {ACM} Symposium on Theory of Computing,
May 28-30, 1986, Berkeley, California, {USA}},
pages = {21--29},
publisher = {{ACM}},
year = {1986},
url = {https://doi.org/10.1145/12130.12133},
doi = {10.1145/12130.12133},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/Cai86.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-05-08 21:46 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
