Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, and Penghui Yao. The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 30:1-30:71, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dong_et_al:LIPIcs.CCC.2024.30, author = {Dong, Yangjing and Fu, Honghao and Natarajan, Anand and Qin, Minglong and Xu, Haochen and Yao, Penghui}, title = {{The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {30:1--30:71}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.30}, URN = {urn:nbn:de:0030-drops-204263}, doi = {10.4230/LIPIcs.CCC.2024.30}, annote = {Keywords: Interactive proofs, Quantum complexity theory, Quantum entanglement, Fourier analysis, Matrix analysis, Invariance principle, Derandomization, PCP, Locally testable code, Positivity testing} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Noel Arteche, Erfan Khaniki, Ján Pich, and Rahul Santhanam. From Proof Complexity to Circuit Complexity via Interactive Protocols. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arteche_et_al:LIPIcs.ICALP.2024.12, author = {Arteche, Noel and Khaniki, Erfan and Pich, J\'{a}n and Santhanam, Rahul}, title = {{From Proof Complexity to Circuit Complexity via Interactive Protocols}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {12:1--12:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.12}, URN = {urn:nbn:de:0030-drops-201557}, doi = {10.4230/LIPIcs.ICALP.2024.12}, annote = {Keywords: proof complexity, circuit complexity, interactive protocols} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha. NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{baraskar_et_al:LIPIcs.ICALP.2024.16, author = {Baraskar, Omkar and Dewan, Agrim and Saha, Chandan and Sinha, Pulkit}, title = {{NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {16:1--16:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.16}, URN = {urn:nbn:de:0030-drops-201598}, doi = {10.4230/LIPIcs.ICALP.2024.16}, annote = {Keywords: Equivalence testing, MCSP, sparse polynomials, 3SAT} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Ben Lund and Aditya Potukuchi. On the List Recoverability of Randomly Punctured Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 30:1-30:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{lund_et_al:LIPIcs.APPROX/RANDOM.2020.30, author = {Lund, Ben and Potukuchi, Aditya}, title = {{On the List Recoverability of Randomly Punctured Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {30:1--30:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.30}, URN = {urn:nbn:de:0030-drops-126330}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.30}, annote = {Keywords: List recovery, randomly punctured codes, Reed-Solomon codes} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, and Dmitry Sokolov. Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 28:1-28:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{derezende_et_al:LIPIcs.CCC.2020.28, author = {de Rezende, Susanna F. and Nordstr\"{o}m, Jakob and Risse, Kilian and Sokolov, Dmitry}, title = {{Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {28:1--28:24}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.28}, URN = {urn:nbn:de:0030-drops-125804}, doi = {10.4230/LIPIcs.CCC.2020.28}, annote = {Keywords: proof complexity, resolution, weak pigeonhole principle, perfect matching, sparse graphs} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Andreas Björklund, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Approximate Counting of k-Paths: Deterministic and in Polynomial Space. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2019.24, author = {Bj\"{o}rklund, Andreas and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav}, title = {{Approximate Counting of k-Paths: Deterministic and in Polynomial Space}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {24:1--24:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.24}, URN = {urn:nbn:de:0030-drops-106001}, doi = {10.4230/LIPIcs.ICALP.2019.24}, annote = {Keywords: parameterized complexity, approximate counting, \{ k\}-Path} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Ben Lund, Adam Sheffer, and Frank de Zeeuw. Bisector Energy and Few Distinct Distances. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 537-552, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{lund_et_al:LIPIcs.SOCG.2015.537, author = {Lund, Ben and Sheffer, Adam and de Zeeuw, Frank}, title = {{Bisector Energy and Few Distinct Distances}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {537--552}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.537}, URN = {urn:nbn:de:0030-drops-51086}, doi = {10.4230/LIPIcs.SOCG.2015.537}, annote = {Keywords: Combinatorial geometry, distinct distances, incidence geometry} }