Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Svyatoslav Gryaznov, Pavel Pudlák, and Navid Talebanfard. Linear Branching Programs and Directional Affine Extractors. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 4:1-4:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{gryaznov_et_al:LIPIcs.CCC.2022.4, author = {Gryaznov, Svyatoslav and Pudl\'{a}k, Pavel and Talebanfard, Navid}, title = {{Linear Branching Programs and Directional Affine Extractors}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {4:1--4:16}, 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.4}, URN = {urn:nbn:de:0030-drops-165664}, doi = {10.4230/LIPIcs.CCC.2022.4}, annote = {Keywords: Boolean Functions, Average-Case Lower Bounds, AC0\lbrack2\rbrack, Affine Dispersers, Affine Extractors} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Erfan Khaniki. Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 17:1-17:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{khaniki:LIPIcs.CCC.2022.17, author = {Khaniki, Erfan}, title = {{Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {17:1--17:15}, 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.17}, URN = {urn:nbn:de:0030-drops-165799}, doi = {10.4230/LIPIcs.CCC.2022.17}, annote = {Keywords: Proof complexity, Bounded arithmetic, Bounded depth Frege, Nisan-Wigderson generators, Meta-complexity, Lower bounds} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Sivaramakrishnan Natarajan Ramamoorthy and Cyrus Rashtchian. Equivalence of Systematic Linear Data Structures and Matrix Rigidity. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 35:1-35:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{natarajanramamoorthy_et_al:LIPIcs.ITCS.2020.35, author = {Natarajan Ramamoorthy, Sivaramakrishnan and Rashtchian, Cyrus}, title = {{Equivalence of Systematic Linear Data Structures and Matrix Rigidity}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {35:1--35:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.35}, URN = {urn:nbn:de:0030-drops-117204}, doi = {10.4230/LIPIcs.ITCS.2020.35}, annote = {Keywords: matrix rigidity, systematic linear data structures, cell probe model, communication complexity} }
Published in: Dagstuhl Reports, Volume 8, Issue 1 (2018)
Albert Atserias, Jakob Nordström, Pavel Pudlák, and Rahul Santhanam. Proof Complexity (Dagstuhl Seminar 18051). In Dagstuhl Reports, Volume 8, Issue 1, pp. 124-157, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@Article{atserias_et_al:DagRep.8.1.124, author = {Atserias, Albert and Nordstr\"{o}m, Jakob and Pudl\'{a}k, Pavel and Santhanam, Rahul}, title = {{Proof Complexity (Dagstuhl Seminar 18051)}}, pages = {124--157}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2018}, volume = {8}, number = {1}, editor = {Atserias, Albert and Nordstr\"{o}m, Jakob and Pudl\'{a}k, Pavel and Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.1.124}, URN = {urn:nbn:de:0030-drops-92864}, doi = {10.4230/DagRep.8.1.124}, annote = {Keywords: bounded arithmetic, computational complexity, logic, proof complexity, satisfiability algorithms} }
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 79, 32nd Computational Complexity Conference (CCC 2017)
Mateus de Oliveira Oliveira and Pavel Pudlák. Representations of Monotone Boolean Functions by Linear Programs. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 3:1-3:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{deoliveiraoliveira_et_al:LIPIcs.CCC.2017.3, author = {de Oliveira Oliveira, Mateus and Pudl\'{a}k, Pavel}, title = {{Representations of Monotone Boolean Functions by Linear Programs}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {3:1--3:14}, 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.3}, URN = {urn:nbn:de:0030-drops-75200}, doi = {10.4230/LIPIcs.CCC.2017.3}, annote = {Keywords: Monotone Linear Programming Circuits, Lov\'{a}sz-Schrijver Proof System, Cutting-Planes Proof System, Feasible Interpolation, Lower Bounds} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Pavel Pudlák, Dominik Scheder, and Navid Talebanfard. Tighter Hard Instances for PPSZ. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 85:1-85:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{pudlak_et_al:LIPIcs.ICALP.2017.85, author = {Pudl\'{a}k, Pavel and Scheder, Dominik and Talebanfard, Navid}, title = {{Tighter Hard Instances for PPSZ}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {85:1--85:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.85}, URN = {urn:nbn:de:0030-drops-74144}, doi = {10.4230/LIPIcs.ICALP.2017.85}, annote = {Keywords: k-SAT, Strong Exponential Time Hypothesis, PPSZ, Resolution} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Yuval Filmus, Pavel Hrubeš, and Massimo Lauria. Semantic Versus Syntactic Cutting Planes. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 35:1-35:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{filmus_et_al:LIPIcs.STACS.2016.35, author = {Filmus, Yuval and Hrube\v{s}, Pavel and Lauria, Massimo}, title = {{Semantic Versus Syntactic Cutting Planes}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {35:1--35:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.35}, URN = {urn:nbn:de:0030-drops-57367}, doi = {10.4230/LIPIcs.STACS.2016.35}, annote = {Keywords: proof complexity, cutting planes, lower bounds} }
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} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Dmitry Gavinsky and Pavel Pudlák. Partition Expanders. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 325-336, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{gavinsky_et_al:LIPIcs.STACS.2014.325, author = {Gavinsky, Dmitry and Pudl\'{a}k, Pavel}, title = {{Partition Expanders}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {325--336}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.325}, URN = {urn:nbn:de:0030-drops-44684}, doi = {10.4230/LIPIcs.STACS.2014.325}, annote = {Keywords: partitions, expanders, communication, complexity} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Pavel Pudlák. On extracting computations from propositional proofs (a survey). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 30-41, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{pudlak:LIPIcs.FSTTCS.2010.30, author = {Pudl\'{a}k, Pavel}, title = {{On extracting computations from propositional proofs (a survey)}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {30--41}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.30}, URN = {urn:nbn:de:0030-drops-28512}, doi = {10.4230/LIPIcs.FSTTCS.2010.30}, annote = {Keywords: proof complexity, propositional tautology, boolean circuits, resolution, feasible interpolation} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, and Rüdiger Reischuk. 06111 Executive Summary – Complexity of Boolean Functions. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)
@InProceedings{krause_et_al:DagSemProc.06111.2, author = {Krause, Matthias and van Melkebeek, Dieter and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger}, title = {{06111 Executive Summary – Complexity of Boolean Functions}}, booktitle = {Complexity of Boolean Functions}, pages = {1--5}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6111}, editor = {Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.2}, URN = {urn:nbn:de:0030-drops-8409}, doi = {10.4230/DagSemProc.06111.2}, annote = {Keywords: Boolean and quantum circuits, discrete problems, computational complexity, lower bounds, communication complexity, proof and query complexity, randomization, pseudo-randomness, derandomization, approximation, cryptography, computational learning} }
Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, and Dieter van Melkebeek. 06111 Abstracts Collection – Complexity of Boolean Functions. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)
@InProceedings{krause_et_al:DagSemProc.06111.1, author = {Krause, Matthias and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger and van Melkebeek, Dieter}, title = {{06111 Abstracts Collection – Complexity of Boolean Functions}}, booktitle = {Complexity of Boolean Functions}, pages = {1--24}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6111}, editor = {Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.1}, URN = {urn:nbn:de:0030-drops-7593}, doi = {10.4230/DagSemProc.06111.1}, annote = {Keywords: Complexity of Boolean functions, Boolean circuits, binary decision diagrams, lower bound proof techniques, combinatorics of Boolean functions, communi algorithmic learning, cryptography, derandomization} }
Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)
Andreas Goerdt, Pavel Pudlák, Uwe Schöning, and Osamu Watanabe. The Propositional Satisfiability Problem -- Algorithms and Lower Bounds (Dagstuhl Seminar 03141). Dagstuhl Seminar Report 374, pp. 1-5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2003)
@TechReport{goerdt_et_al:DagSemRep.374, author = {Goerdt, Andreas and Pudl\'{a}k, Pavel and Sch\"{o}ning, Uwe and Watanabe, Osamu}, title = {{The Propositional Satisfiability Problem -- Algorithms and Lower Bounds (Dagstuhl Seminar 03141)}}, pages = {1--5}, ISSN = {1619-0203}, year = {2003}, type = {Dagstuhl Seminar Report}, number = {374}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.374}, URN = {urn:nbn:de:0030-drops-152545}, doi = {10.4230/DagSemRep.374}, }
Feedback for Dagstuhl Publishing