Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Mitali Bafna and Dor Minzer. Solving Unique Games over Globally Hypercontractive Graphs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bafna_et_al:LIPIcs.CCC.2024.3, author = {Bafna, Mitali and Minzer, Dor}, title = {{Solving Unique Games over Globally Hypercontractive Graphs}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {3:1--3:15}, 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.3}, URN = {urn:nbn:de:0030-drops-203996}, doi = {10.4230/LIPIcs.CCC.2024.3}, annote = {Keywords: unique games, approximation algorithms} }
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)
Yu Chen and Zihan Tan. Lower Bounds on 0-Extension with Steiner Nodes. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 47:1-47:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.47, author = {Chen, Yu and Tan, Zihan}, title = {{Lower Bounds on 0-Extension with Steiner Nodes}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {47:1--47:18}, 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.47}, URN = {urn:nbn:de:0030-drops-201905}, doi = {10.4230/LIPIcs.ICALP.2024.47}, annote = {Keywords: Graph Algorithms, Zero Extension, Integrality Gap} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič. Computing Tree Decompositions with Small Independence Number. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dallard_et_al:LIPIcs.ICALP.2024.51, author = {Dallard, Cl\'{e}ment and Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Milani\v{c}, Martin}, title = {{Computing Tree Decompositions with Small Independence Number}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {51:1--51:18}, 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.51}, URN = {urn:nbn:de:0030-drops-201945}, doi = {10.4230/LIPIcs.ICALP.2024.51}, annote = {Keywords: tree-independence number, approximation, parameterized algorithms} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi. A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{carlson_et_al:LIPIcs.ICALP.2024.35, author = {Carlson, Charlie and Davies, Ewan and Kolla, Alexandra and Potukuchi, Aditya}, title = {{A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {35:1--35:18}, 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.35}, URN = {urn:nbn:de:0030-drops-201782}, doi = {10.4230/LIPIcs.ICALP.2024.35}, annote = {Keywords: approximate counting, independent sets, bipartite graphs, graph containers} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shuangle Li, Bingkai Lin, and Yuwei Liu. Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 107:1-107:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li_et_al:LIPIcs.ICALP.2024.107, author = {Li, Shuangle and Lin, Bingkai and Liu, Yuwei}, title = {{Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {107:1--107: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.107}, URN = {urn:nbn:de:0030-drops-202500}, doi = {10.4230/LIPIcs.ICALP.2024.107}, annote = {Keywords: Nearest Codeword Problem, Hardness of Approximations, Fine-grained Complexity, Parameterized Complexity, Minimum Distance Problem, Shortest Vector Problem} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Agastya Vibhuti Jha and Akash Kumar. A Sublinear Time Tester for Max-Cut on Clusterable Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 91:1-91:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jha_et_al:LIPIcs.ICALP.2024.91, author = {Jha, Agastya Vibhuti and Kumar, Akash}, title = {{A Sublinear Time Tester for Max-Cut on Clusterable Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {91:1--91:17}, 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.91}, URN = {urn:nbn:de:0030-drops-202344}, doi = {10.4230/LIPIcs.ICALP.2024.91}, annote = {Keywords: Sublinear Algorithms, Graph Algorithms, Clusterable Graphs, Property Testung} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yury Makarychev, Max Ovsiankin, and Erasmo Tani. Approximation Algorithms for 𝓁_p-Shortest Path and 𝓁_p-Group Steiner Tree. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 111:1-111:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{makarychev_et_al:LIPIcs.ICALP.2024.111, author = {Makarychev, Yury and Ovsiankin, Max and Tani, Erasmo}, title = {{Approximation Algorithms for 𝓁\underlinep-Shortest Path and 𝓁\underlinep-Group Steiner Tree}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {111:1--111: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.111}, URN = {urn:nbn:de:0030-drops-202542}, doi = {10.4230/LIPIcs.ICALP.2024.111}, annote = {Keywords: Shortest Path, Asymmetric Group Steiner Tree, Sum-of-Squares} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Orestis Plevrakis, Seyoon Ragavan, and S. Matthew Weinberg. On the Cut-Query Complexity of Approximating Max-Cut. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 115:1-115:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{plevrakis_et_al:LIPIcs.ICALP.2024.115, author = {Plevrakis, Orestis and Ragavan, Seyoon and Weinberg, S. Matthew}, title = {{On the Cut-Query Complexity of Approximating Max-Cut}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {115:1--115: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.115}, URN = {urn:nbn:de:0030-drops-202587}, doi = {10.4230/LIPIcs.ICALP.2024.115}, annote = {Keywords: query complexity, maximum cut, approximation algorithms, graph sparsification} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sushant Sachdeva, Anvith Thudi, and Yibin Zhao. Better Sparsifiers for Directed Eulerian Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 119:1-119:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{sachdeva_et_al:LIPIcs.ICALP.2024.119, author = {Sachdeva, Sushant and Thudi, Anvith and Zhao, Yibin}, title = {{Better Sparsifiers for Directed Eulerian Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {119:1--119: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.119}, URN = {urn:nbn:de:0030-drops-202628}, doi = {10.4230/LIPIcs.ICALP.2024.119}, annote = {Keywords: Graph algorithms, Linear algebra and computation, Discrepancy theory} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Antoine Mottet, Tomáš Nagy, and Michael Pinsker. An Order out of Nowhere: A New Algorithm for Infinite-Domain {CSP}s. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 148:1-148:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mottet_et_al:LIPIcs.ICALP.2024.148, author = {Mottet, Antoine and Nagy, Tom\'{a}\v{s} and Pinsker, Michael}, title = {{An Order out of Nowhere: A New Algorithm for Infinite-Domain \{CSP\}s}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {148:1--148:18}, 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.148}, URN = {urn:nbn:de:0030-drops-202912}, doi = {10.4230/LIPIcs.ICALP.2024.148}, annote = {Keywords: Constraint Satisfaction Problems, Hypergraphs, Polymorphisms} }
Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)
Prasad Raghavendra. On Measuring Average Case Complexity via Sum-Of-Squares Degree (Invited Talk). In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{raghavendra:LIPIcs.FSTTCS.2023.2, author = {Raghavendra, Prasad}, title = {{On Measuring Average Case Complexity via Sum-Of-Squares Degree}}, booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-304-1}, ISSN = {1868-8969}, year = {2023}, volume = {284}, editor = {Bouyer, Patricia and Srinivasan, Srikanth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.2}, URN = {urn:nbn:de:0030-drops-193750}, doi = {10.4230/LIPIcs.FSTTCS.2023.2}, annote = {Keywords: semidefinite programming, sum-of-squares SDP, average case complexity, random SAT, stochastic block models} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Jun-Ting Hsieh and Pravesh K. Kothari. Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 77:1-77:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hsieh_et_al:LIPIcs.ICALP.2023.77, author = {Hsieh, Jun-Ting and Kothari, Pravesh K.}, title = {{Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {77:1--77:7}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.77}, URN = {urn:nbn:de:0030-drops-181291}, doi = {10.4230/LIPIcs.ICALP.2023.77}, annote = {Keywords: Max-Cut, approximation algorithm, semidefinite programming} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Prayaag Venkat. Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 98:1-98:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{venkat:LIPIcs.ITCS.2023.98, author = {Venkat, Prayaag}, title = {{Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {98:1--98:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.98}, URN = {urn:nbn:de:0030-drops-176015}, doi = {10.4230/LIPIcs.ITCS.2023.98}, annote = {Keywords: Average-case discrepancy theory, lattices, shortest vector problem} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Jun-Ting Hsieh, Sidhanth Mohanty, and Jeff Xu. Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hsieh_et_al:LIPIcs.CCC.2022.11, author = {Hsieh, Jun-Ting and Mohanty, Sidhanth and Xu, Jeff}, title = {{Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {11:1--11:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.11}, URN = {urn:nbn:de:0030-drops-165735}, doi = {10.4230/LIPIcs.CCC.2022.11}, annote = {Keywords: constraint satisfaction problems, certified counting, random graphs} }