Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Theodoros Papamakarios. A Super-Polynomial Separation Between Resolution and Cut-Free Sequent Calculus. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 74:1-74:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{papamakarios:LIPIcs.MFCS.2023.74, author = {Papamakarios, Theodoros}, title = {{A Super-Polynomial Separation Between Resolution and Cut-Free Sequent Calculus}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {74:1--74:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.74}, URN = {urn:nbn:de:0030-drops-186085}, doi = {10.4230/LIPIcs.MFCS.2023.74}, annote = {Keywords: Proof Complexity, Resolution, Cut-free LK} }
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-dev.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 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Theodoros Papamakarios and Alexander Razborov. Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 100:1-100:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{papamakarios_et_al:LIPIcs.ICALP.2022.100, author = {Papamakarios, Theodoros and Razborov, Alexander}, title = {{Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {100:1--100:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.100}, URN = {urn:nbn:de:0030-drops-164419}, doi = {10.4230/LIPIcs.ICALP.2022.100}, annote = {Keywords: Proof Complexity, Resolution, Size-Space Trade-offs} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Noah Fleming, Toniann Pitassi, and Robert Robere. Extremely Deep Proofs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 70:1-70:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fleming_et_al:LIPIcs.ITCS.2022.70, author = {Fleming, Noah and Pitassi, Toniann and Robere, Robert}, title = {{Extremely Deep Proofs}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {70:1--70:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.70}, URN = {urn:nbn:de:0030-drops-156665}, doi = {10.4230/LIPIcs.ITCS.2022.70}, annote = {Keywords: Proof Complexity, Tradeoffs, Resolution, Cutting Planes} }
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-dev.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)
Shuo Pang. SOS Lower Bound for Exact Planted Clique. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 26:1-26:63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{pang:LIPIcs.CCC.2021.26, author = {Pang, Shuo}, title = {{SOS Lower Bound for Exact Planted Clique}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {26:1--26:63}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.26}, URN = {urn:nbn:de:0030-drops-143000}, doi = {10.4230/LIPIcs.CCC.2021.26}, annote = {Keywords: Sum-of-Squares, planted clique, random graphs, average-case lower bound} }
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-dev.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 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Rahul Santhanam. Pseudorandomness and the Minimum Circuit Size Problem. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 68:1-68:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{santhanam:LIPIcs.ITCS.2020.68, author = {Santhanam, Rahul}, title = {{Pseudorandomness and the Minimum Circuit Size Problem}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {68:1--68:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.68}, URN = {urn:nbn:de:0030-drops-117532}, doi = {10.4230/LIPIcs.ITCS.2020.68}, annote = {Keywords: Minimum Circuit Size Problem, Pseudorandomness, Average-case Complexity, Natural Proofs, Universality Conjecture} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, and Rahul Santhanam. Beyond Natural Proofs: Hardness Magnification and Locality. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 70:1-70:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chen_et_al:LIPIcs.ITCS.2020.70, author = {Chen, Lijie and Hirahara, Shuichi and Oliveira, Igor C. and Pich, J\'{a}n and Rajgopal, Ninad and Santhanam, Rahul}, title = {{Beyond Natural Proofs: Hardness Magnification and Locality}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {70:1--70:48}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.70}, URN = {urn:nbn:de:0030-drops-117550}, doi = {10.4230/LIPIcs.ITCS.2020.70}, annote = {Keywords: Hardness Magnification, Natural Proofs, Minimum Circuit Size Problem, Circuit Lower Bounds} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan. Parity Helps to Compute Majority. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{oliveira_et_al:LIPIcs.CCC.2019.23, author = {Oliveira, Igor Carboni and Santhanam, Rahul and Srinivasan, Srikanth}, title = {{Parity Helps to Compute Majority}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {23:1--23:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.23}, URN = {urn:nbn:de:0030-drops-108453}, doi = {10.4230/LIPIcs.CCC.2019.23}, annote = {Keywords: Computational Complexity, Boolean Circuits, Lower Bounds, Parity, Majority} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Ian Mertz, Toniann Pitassi, and Yuanhao Wei. Short Proofs Are Hard to Find. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{mertz_et_al:LIPIcs.ICALP.2019.84, author = {Mertz, Ian and Pitassi, Toniann and Wei, Yuanhao}, title = {{Short Proofs Are Hard to Find}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {84:1--84:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.84}, URN = {urn:nbn:de:0030-drops-106605}, doi = {10.4230/LIPIcs.ICALP.2019.84}, annote = {Keywords: automatizability, Resolution, SAT solvers, proof complexity} }
Published in: Dagstuhl Seminar Proceedings, Volume 10211, Flexible Network Design (2010)
Friedrich Eisenbrand, Nicolai Hähnle, Alexander Razborov, and Thomas Rothvoß. Diameter of Polyhedra: Limits of Abstraction. In Flexible Network Design. Dagstuhl Seminar Proceedings, Volume 10211, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{eisenbrand_et_al:DagSemProc.10211.2, author = {Eisenbrand, Friedrich and H\"{a}hnle, Nicolai and Razborov, Alexander and Rothvo{\ss}, Thomas}, title = {{Diameter of Polyhedra: Limits of Abstraction}}, booktitle = {Flexible Network Design}, pages = {1--5}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10211}, editor = {Anupam Gupta and Stefano Leonardi and Berthold V\"{o}cking and Roger Wattenhofer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10211.2}, URN = {urn:nbn:de:0030-drops-27247}, doi = {10.4230/DagSemProc.10211.2}, annote = {Keywords: Polyhedra, Graphs} }
Feedback for Dagstuhl Publishing