Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Yaroslav Alekseev, Yuval Filmus, and Alexander Smal. Lifting Dichotomies. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{alekseev_et_al:LIPIcs.CCC.2024.9, author = {Alekseev, Yaroslav and Filmus, Yuval and Smal, Alexander}, title = {{Lifting Dichotomies}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {9:1--9:18}, 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.9}, URN = {urn:nbn:de:0030-drops-204051}, doi = {10.4230/LIPIcs.CCC.2024.9}, annote = {Keywords: decision trees, log-rank conjecture, lifting, parity decision trees} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Noel Arteche, Gaia Carenini, and Matthew Gray. Quantum Automating TC⁰-Frege Is LWE-Hard. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 15:1-15:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arteche_et_al:LIPIcs.CCC.2024.15, author = {Arteche, Noel and Carenini, Gaia and Gray, Matthew}, title = {{Quantum Automating TC⁰-Frege Is LWE-Hard}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {15:1--15:25}, 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.15}, URN = {urn:nbn:de:0030-drops-204117}, doi = {10.4230/LIPIcs.CCC.2024.15}, annote = {Keywords: automatability, post-quantum cryptography, feasible interpolation} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Theodoros Papamakarios. Depth-d Frege Systems Are Not Automatable Unless 𝖯 = NP. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{papamakarios:LIPIcs.CCC.2024.22, author = {Papamakarios, Theodoros}, title = {{Depth-d Frege Systems Are Not Automatable Unless 𝖯 = NP}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {22:1--22:17}, 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.22}, URN = {urn:nbn:de:0030-drops-204187}, doi = {10.4230/LIPIcs.CCC.2024.22}, annote = {Keywords: Proof complexity, Automatability, Bounded-depth Frege} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, and Pavel Dvořák. Exponential Separation Between Powers of Regular and General Resolution over Parities. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 23:1-23:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bhattacharya_et_al:LIPIcs.CCC.2024.23, author = {Bhattacharya, Sreejata Kishor and Chattopadhyay, Arkadev and Dvo\v{r}\'{a}k, Pavel}, title = {{Exponential Separation Between Powers of Regular and General Resolution over Parities}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {23:1--23:32}, 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.23}, URN = {urn:nbn:de:0030-drops-204191}, doi = {10.4230/LIPIcs.CCC.2024.23}, annote = {Keywords: Proof Complexity, Regular Reslin, Branching Programs, Lifting} }
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)
Shalev Ben-David and Srijita Kundu. Oracle Separation of QMA and QCMA with Bounded Adaptivity. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bendavid_et_al:LIPIcs.ICALP.2024.21, author = {Ben-David, Shalev and Kundu, Srijita}, title = {{Oracle Separation of QMA and QCMA with Bounded Adaptivity}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {21:1--21: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.21}, URN = {urn:nbn:de:0030-drops-201642}, doi = {10.4230/LIPIcs.ICALP.2024.21}, annote = {Keywords: Quantum computing, computational complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Bruno Loff and Mateusz Skomra. Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 147:1-147:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{loff_et_al:LIPIcs.ICALP.2024.147, author = {Loff, Bruno and Skomra, Mateusz}, title = {{Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {147:1--147:16}, 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.147}, URN = {urn:nbn:de:0030-drops-202908}, doi = {10.4230/LIPIcs.ICALP.2024.147}, annote = {Keywords: Mean-payoff games, discounted games, policy iteration, smoothed analysis} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Michaela Borzechowski, John Fearnley, Spencer Gordon, Rahul Savani, Patrick Schnider, and Simon Weber. Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{borzechowski_et_al:LIPIcs.ICALP.2024.32, author = {Borzechowski, Michaela and Fearnley, John and Gordon, Spencer and Savani, Rahul and Schnider, Patrick and Weber, Simon}, title = {{Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {32:1--32: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.32}, URN = {urn:nbn:de:0030-drops-201751}, doi = {10.4230/LIPIcs.ICALP.2024.32}, annote = {Keywords: P-LCP, Unique Sink Orientation, \alpha-Ham Sandwich, search complexity, TFNP, UEOPL} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, and Marc Vinyals. Proving Unsatisfiability with Hitting Formulas. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 48:1-48:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{filmus_et_al:LIPIcs.ITCS.2024.48, author = {Filmus, Yuval and Hirsch, Edward A. and Riazanov, Artur and Smal, Alexander and Vinyals, Marc}, title = {{Proving Unsatisfiability with Hitting Formulas}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {48:1--48:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.48}, URN = {urn:nbn:de:0030-drops-195762}, doi = {10.4230/LIPIcs.ITCS.2024.48}, annote = {Keywords: hitting formulas, polynomial identity testing, query complexity} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Lukáš Folwarczný, Mika Göös, Pavel Hubáček, Gilbert Maystre, and Weiqiang Yuan. One-Way Functions vs. TFNP: Simpler and Improved. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{folwarczny_et_al:LIPIcs.ITCS.2024.50, author = {Folwarczn\'{y}, Luk\'{a}\v{s} and G\"{o}\"{o}s, Mika and Hub\'{a}\v{c}ek, Pavel and Maystre, Gilbert and Yuan, Weiqiang}, title = {{One-Way Functions vs. TFNP: Simpler and Improved}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {50:1--50:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.50}, URN = {urn:nbn:de:0030-drops-195788}, doi = {10.4230/LIPIcs.ITCS.2024.50}, annote = {Keywords: TFNP, One-Way Functions, Oracle, Separation, Black-Box} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov. Sampling and Certifying Symmetric Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{filmus_et_al:LIPIcs.APPROX/RANDOM.2023.36, author = {Filmus, Yuval and Leigh, Itai and Riazanov, Artur and Sokolov, Dmitry}, title = {{Sampling and Certifying Symmetric Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {36:1--36:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.36}, URN = {urn:nbn:de:0030-drops-188611}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.36}, annote = {Keywords: sampling, lower bounds, robust sunflowers, decision trees, switching networks} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Mika Göös, Ziyi Guan, and Tiberiu Mosnoi. Depth-3 Circuits for Inner Product. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 51:1-51:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{goos_et_al:LIPIcs.MFCS.2023.51, author = {G\"{o}\"{o}s, Mika and Guan, Ziyi and Mosnoi, Tiberiu}, title = {{Depth-3 Circuits for Inner Product}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {51:1--51:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.51}, URN = {urn:nbn:de:0030-drops-185856}, doi = {10.4230/LIPIcs.MFCS.2023.51}, annote = {Keywords: Circuit complexity, inner product} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami, and Kaave Hosseini. Online Learning and Disambiguations of Partial Concept Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cheung_et_al:LIPIcs.ICALP.2023.42, author = {Cheung, Tsun-Ming and Hatami, Hamed and Hatami, Pooya and Hosseini, Kaave}, title = {{Online Learning and Disambiguations of Partial Concept Classes}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {42:1--42:13}, 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.42}, URN = {urn:nbn:de:0030-drops-180946}, doi = {10.4230/LIPIcs.ICALP.2023.42}, annote = {Keywords: Online learning, Littlestone dimension, VC dimension, partial concept class, clique vs independent set, Alon-Saks-Seymour conjecture, Standard Optimal Algorithm, PAC learning} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Sam Buss, Noah Fleming, and Russell Impagliazzo. TFNP Characterizations of Proof Systems and Monotone Circuits. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 30:1-30:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{buss_et_al:LIPIcs.ITCS.2023.30, author = {Buss, Sam and Fleming, Noah and Impagliazzo, Russell}, title = {{TFNP Characterizations of Proof Systems and Monotone Circuits}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {30:1--30:40}, 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.30}, URN = {urn:nbn:de:0030-drops-175332}, doi = {10.4230/LIPIcs.ITCS.2023.30}, annote = {Keywords: Proof Complexity, Circuit Complexity, TFNP} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Mika Göös and Siddhartha Jain. Communication Complexity of Collision. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 19:1-19:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{goos_et_al:LIPIcs.APPROX/RANDOM.2022.19, author = {G\"{o}\"{o}s, Mika and Jain, Siddhartha}, title = {{Communication Complexity of Collision}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {19:1--19:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.19}, URN = {urn:nbn:de:0030-drops-171415}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.19}, annote = {Keywords: Collision, Communication complexity, Lifting} }