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 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 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)
Sergei Ovcharov. OBDD(Join) Proofs Cannot Be Balanced. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 72:1-72:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ovcharov:LIPIcs.MFCS.2023.72, author = {Ovcharov, Sergei}, title = {{OBDD(Join) Proofs Cannot Be Balanced}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {72:1--72:13}, 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.72}, URN = {urn:nbn:de:0030-drops-186065}, doi = {10.4230/LIPIcs.MFCS.2023.72}, annote = {Keywords: Proof complexity, OBDD, lower bounds, depth of proofs} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Russell Impagliazzo, Sasank Mouli, and Toniann Pitassi. Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{impagliazzo_et_al:LIPIcs.CCC.2023.7, author = {Impagliazzo, Russell and Mouli, Sasank and Pitassi, Toniann}, title = {{Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {7:1--7:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.7}, URN = {urn:nbn:de:0030-drops-182774}, doi = {10.4230/LIPIcs.CCC.2023.7}, annote = {Keywords: Proof complexity, Algebraic proof systems, Polynomial Calculus, Extension variables, AC⁰\lbrackp\rbrack-Frege} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Dmitry Itsykson and Artur Riazanov. Automating OBDD proofs is NP-hard. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{itsykson_et_al:LIPIcs.MFCS.2022.59, author = {Itsykson, Dmitry and Riazanov, Artur}, title = {{Automating OBDD proofs is NP-hard}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {59:1--59:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.59}, URN = {urn:nbn:de:0030-drops-168575}, doi = {10.4230/LIPIcs.MFCS.2022.59}, annote = {Keywords: proof complexity, OBDD, automatability, lifting, dag-like communication} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Dmitry Sokolov. Pseudorandom Generators, Resolution and Heavy Width. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{sokolov:LIPIcs.CCC.2022.15, author = {Sokolov, Dmitry}, title = {{Pseudorandom Generators, Resolution and Heavy Width}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {15:1--15:22}, 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.15}, URN = {urn:nbn:de:0030-drops-165770}, doi = {10.4230/LIPIcs.CCC.2022.15}, annote = {Keywords: proof complexity, pseudorandom generators, resolution, lower bounds} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Dmitry Itsykson and Artur Riazanov. Proof Complexity of Natural Formulas via Communication Arguments. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 3:1-3:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{itsykson_et_al:LIPIcs.CCC.2021.3, author = {Itsykson, Dmitry and Riazanov, Artur}, title = {{Proof Complexity of Natural Formulas via Communication Arguments}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {3:1--3:34}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.3}, URN = {urn:nbn:de:0030-drops-142773}, doi = {10.4230/LIPIcs.CCC.2021.3}, annote = {Keywords: bit pigeonhole principle, disjointness, multiparty communication complexity, perfect matching, proof complexity, randomized communication complexity, Resolution over linear equations, tree-like proofs} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Anastasia Sofronova and Dmitry Sokolov. Branching Programs with Bounded Repetitions and Flow Formulas. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{sofronova_et_al:LIPIcs.CCC.2021.17, author = {Sofronova, Anastasia and Sokolov, Dmitry}, title = {{Branching Programs with Bounded Repetitions and Flow Formulas}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {17:1--17:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.17}, URN = {urn:nbn:de:0030-drops-142915}, doi = {10.4230/LIPIcs.CCC.2021.17}, annote = {Keywords: proof complexity, branching programs, bounded repetitions, lower bounds} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Yaroslav Alekseev. A Lower Bound for Polynomial Calculus with Extension Rule. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{alekseev:LIPIcs.CCC.2021.21, author = {Alekseev, Yaroslav}, title = {{A Lower Bound for Polynomial Calculus with Extension Rule}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {21:1--21:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.21}, URN = {urn:nbn:de:0030-drops-142959}, doi = {10.4230/LIPIcs.CCC.2021.21}, annote = {Keywords: proof complexity, algebraic proofs, polynomial calculus} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Dmitry Sokolov. The Power of Negative Reasoning. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 40:1-40:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{derezende_et_al:LIPIcs.CCC.2021.40, author = {de Rezende, Susanna F. and Lauria, Massimo and Nordstr\"{o}m, Jakob and Sokolov, Dmitry}, title = {{The Power of Negative Reasoning}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {40:1--40:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.40}, URN = {urn:nbn:de:0030-drops-143140}, doi = {10.4230/LIPIcs.CCC.2021.40}, annote = {Keywords: Proof complexity, Polynomial calculus, Nullstellensatz, Sums-of-squares, Sherali-Adams} }