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 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)
Pavel Hubáček, Erfan Khaniki, and Neil Thapen. TFNP Intersections Through the Lens of Feasible Disjunction. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 63:1-63:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hubacek_et_al:LIPIcs.ITCS.2024.63, author = {Hub\'{a}\v{c}ek, Pavel and Khaniki, Erfan and Thapen, Neil}, title = {{TFNP Intersections Through the Lens of Feasible Disjunction}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {63:1--63:24}, 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.63}, URN = {urn:nbn:de:0030-drops-195917}, doi = {10.4230/LIPIcs.ITCS.2024.63}, annote = {Keywords: TFNP, feasible disjunction, proof complexity, TFNP intersection classes} }
Published in: LIPIcs, Volume 271, 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)
Adrián Rebola-Pardo. Even Shorter Proofs Without New Variables. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 271, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{rebolapardo:LIPIcs.SAT.2023.22, author = {Rebola-Pardo, Adri\'{a}n}, title = {{Even Shorter Proofs Without New Variables}}, booktitle = {26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)}, pages = {22:1--22:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-286-0}, ISSN = {1868-8969}, year = {2023}, volume = {271}, editor = {Mahajan, Meena and Slivovsky, Friedrich}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2023.22}, URN = {urn:nbn:de:0030-drops-184844}, doi = {10.4230/LIPIcs.SAT.2023.22}, annote = {Keywords: Interference, SAT solving, Unsatisfiability proofs, Unsatisfiable cores} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Pavel Pudlák and Neil Thapen. Random Resolution Refutations. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 1:1-1:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{pudlak_et_al:LIPIcs.CCC.2017.1, author = {Pudl\'{a}k, Pavel and Thapen, Neil}, title = {{Random Resolution Refutations}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {1:1--1:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.1}, URN = {urn:nbn:de:0030-drops-75235}, doi = {10.4230/LIPIcs.CCC.2017.1}, annote = {Keywords: proof complexity, random, resolution} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Nicola Galesi, Pavel Pudlák, and Neil Thapen. The Space Complexity of Cutting Planes Refutations. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 433-447, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{galesi_et_al:LIPIcs.CCC.2015.433, author = {Galesi, Nicola and Pudl\'{a}k, Pavel and Thapen, Neil}, title = {{The Space Complexity of Cutting Planes Refutations}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {433--447}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.433}, URN = {urn:nbn:de:0030-drops-50551}, doi = {10.4230/LIPIcs.CCC.2015.433}, annote = {Keywords: Proof Complexity, Cutting Planes, Space Complexity} }