Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Jin-Yi Cai and Ben Young. Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cai_et_al:LIPIcs.ICALP.2023.33, author = {Cai, Jin-Yi and Young, Ben}, title = {{Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {33:1--33:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.33}, URN = {urn:nbn:de:0030-drops-180851}, doi = {10.4230/LIPIcs.ICALP.2023.33}, annote = {Keywords: #CSP, Quantum isomorphism, Holant, Gadget, Intertwiners, Planar graphs} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Jin-Yi Cai and Daniel P. Szabo. Bounded Degree Nonnegative Counting CSP. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cai_et_al:LIPIcs.MFCS.2022.27, author = {Cai, Jin-Yi and Szabo, Daniel P.}, title = {{Bounded Degree Nonnegative Counting CSP}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {27:1--27:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.27}, URN = {urn:nbn:de:0030-drops-168250}, doi = {10.4230/LIPIcs.MFCS.2022.27}, annote = {Keywords: Computational Counting Complexity, Constraint Satisfaction Problems, Counting CSPs, Complexity Dichotomy, Nonnegative Counting CSP, Graph Homomorphisms} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Jin-Yi Cai, Tianyu Liu, Pinyan Lu, and Jing Yu. Approximability of the Eight-Vertex Model. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cai_et_al:LIPIcs.CCC.2020.4, author = {Cai, Jin-Yi and Liu, Tianyu and Lu, Pinyan and Yu, Jing}, title = {{Approximability of the Eight-Vertex Model}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {4:1--4:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.4}, URN = {urn:nbn:de:0030-drops-125564}, doi = {10.4230/LIPIcs.CCC.2020.4}, annote = {Keywords: Approximate complexity, the eight-vertex model, Markov chain Monte Carlo} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. From Holant to Quantum Entanglement and Back. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cai_et_al:LIPIcs.ICALP.2020.22, author = {Cai, Jin-Yi and Fu, Zhiguo and Shao, Shuai}, title = {{From Holant to Quantum Entanglement and Back}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {22:1--22:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.22}, URN = {urn:nbn:de:0030-drops-124298}, doi = {10.4230/LIPIcs.ICALP.2020.22}, annote = {Keywords: Holant problem, Quantum entanglement, SLOCC equivalence, Bell property} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Jin-Yi Cai and Tianyu Liu. Counting Perfect Matchings and the Eight-Vertex Model. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cai_et_al:LIPIcs.ICALP.2020.23, author = {Cai, Jin-Yi and Liu, Tianyu}, title = {{Counting Perfect Matchings and the Eight-Vertex Model}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {23:1--23:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.23}, URN = {urn:nbn:de:0030-drops-124301}, doi = {10.4230/LIPIcs.ICALP.2020.23}, annote = {Keywords: Approximate complexity, the eight-vertex model, counting perfect matchings} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Artem Govorov, Jin-Yi Cai, and Martin Dyer. A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 66:1-66:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{govorov_et_al:LIPIcs.ICALP.2020.66, author = {Govorov, Artem and Cai, Jin-Yi and Dyer, Martin}, title = {{A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {66:1--66:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.66}, URN = {urn:nbn:de:0030-drops-124733}, doi = {10.4230/LIPIcs.ICALP.2020.66}, annote = {Keywords: Graph homomorphism, Complexity dichotomy, Counting problems} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Shuai Shao and Yuxin Sun. Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 96:1-96:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{shao_et_al:LIPIcs.ICALP.2020.96, author = {Shao, Shuai and Sun, Yuxin}, title = {{Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {96:1--96:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.96}, URN = {urn:nbn:de:0030-drops-125036}, doi = {10.4230/LIPIcs.ICALP.2020.96}, annote = {Keywords: 2-Spin system, Correlation decay, Zero-freeness, Phase transition, Contraction} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Jin-Yi Cai and Artem Govorov. On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cai_et_al:LIPIcs.ITCS.2020.17, author = {Cai, Jin-Yi and Govorov, Artem}, title = {{On a Theorem of Lov\'{a}sz that hom(⋅, H) Determines the Isomorphism Type of H}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {17:1--17:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.17}, URN = {urn:nbn:de:0030-drops-117022}, doi = {10.4230/LIPIcs.ITCS.2020.17}, annote = {Keywords: Graph homomorphism, Partition function, Complexity dichotomy, Connection matrices and tensors} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Yi-Jun Chang, Wenyu Jin, and Seth Pettie. Simple Contention Resolution via Multiplicative Weight Updates. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chang_et_al:OASIcs.SOSA.2019.16, author = {Chang, Yi-Jun and Jin, Wenyu and Pettie, Seth}, title = {{Simple Contention Resolution via Multiplicative Weight Updates}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {16:1--16:16}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.16}, URN = {urn:nbn:de:0030-drops-100426}, doi = {10.4230/OASIcs.SOSA.2019.16}, annote = {Keywords: Contention resolution, multiplicative weight update method} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, and Michael Kowalczyk. A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{cai_et_al:LIPIcs.ITCS.2018.2, author = {Cai, Jin-Yi and Fu, Zhiguo and Girstmair, Kurt and Kowalczyk, Michael}, title = {{A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {2:1--2:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.2}, URN = {urn:nbn:de:0030-drops-83251}, doi = {10.4230/LIPIcs.ITCS.2018.2}, annote = {Keywords: Spin Systems, Holant Problems, Number Theory, Characters, Cyclotomic Fields} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, and Eric Vigoda. #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 582-595, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{cai_et_al:LIPIcs.APPROX-RANDOM.2014.582, author = {Cai, Jin-Yi and Galanis, Andreas and Goldberg, Leslie Ann and Guo, Heng and Jerrum, Mark and Stefankovic, Daniel and Vigoda, Eric}, 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)}, pages = {582--595}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.582}, URN = {urn:nbn:de:0030-drops-47235}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.582}, annote = {Keywords: Spin systems, approximate counting, complexity, #BIS-hardness, phase transition} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Michael Kowalczyk and Jin-Yi Cai. Holant Problems for Regular Graphs with Complex Edge Functions. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 525-536, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{kowalczyk_et_al:LIPIcs.STACS.2010.2482, author = {Kowalczyk, Michael and Cai, Jin-Yi}, title = {{Holant Problems for Regular Graphs with Complex Edge Functions}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {525--536}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2482}, URN = {urn:nbn:de:0030-drops-24826}, doi = {10.4230/LIPIcs.STACS.2010.2482}, annote = {Keywords: Computational complexity} }
Published in: Dagstuhl Seminar Proceedings, Volume 5321, Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics (2005)
Yi Jin and Michael Thielscher. Actions and Belief Revision : A Computational Approach. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)
@InProceedings{jin_et_al:DagSemProc.05321.5, author = {Jin, Yi and Thielscher, Michael}, title = {{Actions and Belief Revision : A Computational Approach}}, booktitle = {Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics}, pages = {1--25}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2005}, volume = {5321}, editor = {James Delgrande and Jerome Lang and Hans Rott and Jean-Marc Tallon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05321.5}, URN = {urn:nbn:de:0030-drops-3599}, doi = {10.4230/DagSemProc.05321.5}, annote = {Keywords: Iterated Belief Revision, Belief Base Revision, Computational Complexity} }
Feedback for Dagstuhl Publishing