Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Ying Liu and Shiteng Chen. Sub-Exponential Time Lower Bounds for #VC and #Matching on 3-Regular Graphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{liu_et_al:LIPIcs.STACS.2024.49, author = {Liu, Ying and Chen, Shiteng}, title = {{Sub-Exponential Time Lower Bounds for #VC and #Matching on 3-Regular Graphs}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {49:1--49:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.49}, URN = {urn:nbn:de:0030-drops-197593}, doi = {10.4230/LIPIcs.STACS.2024.49}, annote = {Keywords: computational complexity, planar Holant, polynomial interpolation, rETH, sub-exponential, #ETH, #Matching, #VC} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Yumou Fei, Leslie Ann Goldberg, and Pinyan Lu. Two-State Spin Systems with Negative Interactions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 45:1-45:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fei_et_al:LIPIcs.ITCS.2024.45, author = {Fei, Yumou and Goldberg, Leslie Ann and Lu, Pinyan}, title = {{Two-State Spin Systems with Negative Interactions}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {45:1--45:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.45}, URN = {urn:nbn:de:0030-drops-195739}, doi = {10.4230/LIPIcs.ITCS.2024.45}, annote = {Keywords: Approximate Counting, Spin Systems, #P-Hardness, Randomized Algorithms} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia. The Complexity of Weighted Boolean #CSP Modulo k. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 249-260, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{guo_et_al:LIPIcs.STACS.2011.249, author = {Guo, Heng and Huang, Sangxia and Lu, Pinyan and Xia, Mingji}, title = {{The Complexity of Weighted Boolean #CSP Modulo k}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {249--260}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.249}, URN = {urn:nbn:de:0030-drops-30158}, doi = {10.4230/LIPIcs.STACS.2011.249}, annote = {Keywords: #CSP, dichotomy theorem, counting problems, computational complexity} }
Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
Angsheng Li and Mingji Xia. A Theory for Valiant's Matchcircuits (Extended Abstract). In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 491-502, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{li_et_al:LIPIcs.STACS.2008.1368, author = {Li, Angsheng and Xia, Mingji}, title = {{A Theory for Valiant's Matchcircuits}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {491--502}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1368}, URN = {urn:nbn:de:0030-drops-13686}, doi = {10.4230/LIPIcs.STACS.2008.1368}, annote = {Keywords: Pfaffian, Matchgate, Matchcircuit} }
Feedback for Dagstuhl Publishing