Pavel Pudlák

Publication Activity (10 Years)

Years Active: 1975-2024
Publications (10 Years): 35

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

Computational Complexity Conference

Bull. Symb. Log.

Publications

Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Navid Talebanfard
Local Enumeration and Majority Lower Bounds. CoRR (2024)
Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Navid Talebanfard
Local Enumeration and Majority Lower Bounds. CCC (2024)
Pavel Dvorák, Lukas Folwarczny, Michal Opler, Pavel Pudlák, Robert Sámal, Tung Anh Vu
Bounds on Functionality and Symmetric Difference - Two Intriguing Graph Parameters. WG (2023)
Pavel Pudlák
Reviews. Bull. Symb. Log. 29 (4) (2023)
Pavel Dvorák, Lukas Folwarczny, Michal Opler, Pavel Pudlák, Robert Sámal, Tung Anh Vu
Bounds on Functionality and Symmetric Difference - Two Intriguing Graph Parameters. CoRR (2023)
Pavel Pudlák, Vojtech Rödl
Extractors for Small Zero-Fixing Sources. Comb. 42 (4) (2022)
Svyatoslav Gryaznov, Pavel Pudlák, Navid Talebanfard
Linear Branching Programs and Directional Affine Extractors. CoRR (2022)
Svyatoslav Gryaznov, Pavel Pudlák, Navid Talebanfard
Linear Branching Programs and Directional Affine Extractors. CCC (2022)
Pavel Pudlák
On matrices potentially useful for tree codes. Inf. Process. Lett. 174 (2022)
Pavel Pudlák
The canonical pairs of bounded depth Frege systems. Ann. Pure Appl. Log. 172 (2) (2021)
Pavel Pudlák
On matrices potentially useful for tree codes. CoRR (2020)
Dmitry Gavinsky, Pavel Pudlák
Santha-Vazirani sources, deterministic condensers and very strong extractors. Theory Comput. Syst. 64 (6) (2020)
Pavel Pudlák
The canonical pairs of bounded depth Frege systems. CoRR (2019)
Pavel Pudlák, Neil Thapen
Random resolution refutations. Comput. Complex. 28 (2) (2019)
Pavel Pudlák, Vojtech Rödl
Extractors for small zero-fixing sources. CoRR (2019)
Pavel Pudlák, Vojtech Rödl
Extractors for small zero-fixing sources. Electron. Colloquium Comput. Complex. 26 (2019)
Dmitry Gavinsky, Pavel Pudlák
Santha-Vazirani sources, deterministic condensers and very strong extractors. CoRR (2019)
Mateus de Oliveira Oliveira, Pavel Pudlák
Representations of Monotone Boolean Functions by Linear Programs. ACM Trans. Comput. Theory 11 (4) (2019)
Pavel Hrubes, Pavel Pudlák
A note on monotone real circuits. Inf. Process. Lett. 131 (2018)
Daniel Lokshtanov, Ivan Mikhailin, Ramamohan Paturi, Pavel Pudlák
Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth. SODA (2018)
Albert Atserias, Jakob Nordström, Pavel Pudlák, Rahul Santhanam
Proof Complexity (Dagstuhl Seminar 18051). Dagstuhl Reports 8 (1) (2018)
Petr Glivický, Pavel Pudlák
A wild model of linear arithmetic and discretely ordered modules. Math. Log. Q. 63 (6) (2017)
Mateus de Oliveira Oliveira, Pavel Pudlák
Representations of Monotone Boolean Functions by Linear Programs. Electron. Colloquium Comput. Complex. 24 (2017)
Pavel Hrubes, Pavel Pudlák
Random Formulas, Monotone Circuits, and Interpolation. FOCS (2017)
Pavel Pudlák, Dominik Scheder, Navid Talebanfard
Tighter Hard Instances for PPSZ. ICALP (2017)
Pavel Pudlák, Neil Thapen
Random Resolution Refutations. Computational Complexity Conference (2017)
Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen
The complexity of proving that a graph is Ramsey. Comb. 37 (2) (2017)
Pavel Hrubes, Pavel Pudlák
A note on monotone real circuits. Electron. Colloquium Comput. Complex. 24 (2017)
Pavel Hrubes, Pavel Pudlák
Random formulas, monotone circuits, and interpolation. Electron. Colloquium Comput. Complex. 24 (2017)
Pavel Pudlák
Petr Hajek, 1940-2016. Bull. EATCS 121 (2017)
Mateus de Oliveira Oliveira, Pavel Pudlák
Representations of Monotone Boolean Functions by Linear Programs. Computational Complexity Conference (2017)
Pavel Pudlák
Incompleteness in the finite Domain. Bull. Symb. Log. 23 (4) (2017)
Dmitry Gavinsky, Pavel Pudlák
Partition Expanders. Theory Comput. Syst. 60 (3) (2017)
Pavel Pudlák, Neil Thapen
Random resolution refutations. Electron. Colloquium Comput. Complex. 23 (2016)
Pavel Pudlák, Dominik Scheder, Navid Talebanfard
Tighter Hard Instances for PPSZ. CoRR (2016)
Dmitry Gavinsky, Pavel Pudlák
On the Entropy of Locally-Independent Bernoulli Trials. CoRR (2015)
Nicola Galesi, Pavel Pudlák, Neil Thapen
The Space Complexity of Cutting Planes Refutations. Computational Complexity Conference (2015)
Pavel Pudlák
On the complexity of finding falsifying assignments for Herbrand disjunctions. Arch. Math. Log. 54 (7-8) (2015)
Dmitry Gavinsky, Pavel Pudlák
Partition Expanders. CoRR (2014)
Dmitry Gavinsky, Pavel Pudlák
Partition Expanders. STACS (2014)
Arnold Beckmann, Pavel Pudlák, Neil Thapen
Parity Games and Propositional Proofs. ACM Trans. Comput. Log. 15 (2) (2014)
Dmitry Gavinsky, Pavel Pudlák
Partition Expanders. Electron. Colloquium Comput. Complex. 21 (2014)
Nicola Galesi, Pavel Pudlák, Neil Thapen
The space complexity of cutting planes refutations. Electron. Colloquium Comput. Complex. 21 (2014)
Pavel Pudlák
On the complexity of finding falsifying assignments for Herbrand disjunctions. CoRR (2014)
Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates. IEEE Trans. Inf. Theory 59 (10) (2013)
Pavel Pudlák, Arnold Beckmann, Neil Thapen
Parity Games and Propositional Proofs. Electron. Colloquium Comput. Complex. 20 (2013)
Arnold Beckmann, Pavel Pudlák, Neil Thapen
Parity Games and Propositional Proofs. MFCS (2013)
Pavel Pudlák
Linear tree codes and the problem of explicit constructions. CoRR (2013)
Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen
The Complexity of Proving That a Graph Is Ramsey. ICALP (1) (2013)
Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen
The complexity of proving that a graph is Ramsey. Electron. Colloquium Comput. Complex. 20 (2013)
Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen
The complexity of proving that a graph is Ramsey CoRR (2013)
Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. STOC (2012)
Pavel Pudlák
A lower bound on the size of resolution proofs of the Ramsey theorem. Inf. Process. Lett. 112 (14-15) (2012)
Pavel Pudlák, Neil Thapen
Alternating minima and maxima, Nash equilibria and Bounded Arithmetic. Ann. Pure Appl. Log. 163 (5) (2012)
Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák
Pseudorandom generators for group products: extended abstract. STOC (2011)
Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. Electron. Colloquium Comput. Complex. 18 (2011)
Pavel Pudlák
A lower bound on the size of resolution proofs of the Ramsey theorem. Electron. Colloquium Comput. Complex. 18 (2011)
Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák
On convex complexity measures. Theor. Comput. Sci. 411 (16-18) (2010)
Alexandr V. Kostochka, Pavel Pudlák, Vojtech Rödl
Some constructive bounds on Ramsey numbers. J. Comb. Theory, Ser. B 100 (5) (2010)
Ramamohan Paturi, Pavel Pudlák
On the complexity of circuit satisfiability. STOC (2010)
Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák
Pseudorandom Generators for Group Products. Electron. Colloquium Comput. Complex. 17 (2010)
Pavel Pudlák
On extracting computations from propositional proofs (a survey). FSTTCS (2010)
Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák
On convex complexity measures. Electron. Colloquium Comput. Complex. 16 (2009)
Pavel Pudlák
Quantum deduction rules. Ann. Pure Appl. Log. 157 (1) (2009)
Pavel Pudlák
Twelve Problems in Proof Complexity. CSR (2008)
Pavel Pudlák
Fragments of bounded arithmetic and the lengths of proofs. J. Symb. Log. 73 (4) (2008)
Dmitry Gavinsky, Pavel Pudlák
Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity. Computational Complexity Conference (2008)
Dmitry Gavinsky, Pavel Pudlák
Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity. Electron. Colloquium Comput. Complex. 14 (074) (2007)
Pavel Pudlák
Quantum deduction rules. Electron. Colloquium Comput. Complex. 14 (032) (2007)
Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, Dieter van Melkebeek
06111 Abstracts Collection -- Complexity of Boolean Functions. Complexity of Boolean Functions (2006)
Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien
Lower bounds for circuits with MOD_m gates. FOCS (2006)
Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, Rüdiger Reischuk
06111 Executive Summary -- Complexity of Boolean Functions. Complexity of Boolean Functions (2006)
Pavel Pudlák
On Search Problems in Complexity Theory and in Logic (Abstract). CIAC (2006)
Pavel Pudlák
Godel and Computations (Abstract). Computational Complexity Conference (2006)
Pavel Pudlák
Gödel and computations: a 100th anniversary retrospective. SIGACT News 37 (4) (2006)
Michal Koucký, Pavel Pudlák, Denis Thérien
Bounded-depth circuits: separating wires from gates. STOC (2005)
Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane
-SAT. J. ACM 52 (3) (2005)
Pavel Pudlák
A nonlinear bound on the number of wires in bounded depth circuits Electron. Colloquium Comput. Complex. (122) (2005)
Ramamohan Paturi, Pavel Pudlák
Circuit lower bounds and linear codes Electron. Colloquium Comput. Complex. (004) (2004)
Pavel Pudlák
Parallel strategies. J. Symb. Log. 68 (4) (2003)
Pavel Pudlák
On reducibility and symmetry of disjoint NP pairs. Theor. Comput. Sci. 295 (2003)
Pavel Pudlák
An Application of Hindman's Theorem to a Problem on Communication Complexity. Comb. Probab. Comput. 12 (5-6) (2003)
Anna Gál, Pavel Pudlák
A note on monotone complexity and the rank of matrices. Inf. Process. Lett. 87 (6) (2003)
Anna Gál, Pavel Pudlák
Erratum to: "A note on monotone complexity and the rank of matrices": [Information Processing Letters 87 (2003) 321-326]. Inf. Process. Lett. 88 (5) (2003)
Albert Atserias, Nicola Galesi, Pavel Pudlák
Monotone simulations of non-monotone proofs. J. Comput. Syst. Sci. 65 (4) (2002)
Pavel Pudlák
Cycles of Nonzero Elements in Low Rank Matrices. Comb. 22 (2) (2002)
Pavel Pudlák
Monotone complexity and the rank of matrices Electron. Colloquium Comput. Complex. (007) (2002)
Pavel Pudlák
On reducibility and symmetry of disjoint NP-pairs Electron. Colloquium Comput. Complex. 8 (44) (2001)
Pavel Pudlák
Gust Editor's Foreword. J. Comput. Syst. Sci. 63 (2) (2001)
Samuel R. Buss, Pavel Pudlák
On the computational content of intuitionistic propositional proofs. Ann. Pure Appl. Log. 109 (1-2) (2001)
Albert Atserias, Nicola Galesi, Pavel Pudlák
Monotone Simulations of Nonmonotone Proofs. Computational Complexity Conference (2001)
Pavel Pudlák
Complexity Theory and Genetics: The Computational Power of Crossing Over. Inf. Comput. 171 (2) (2001)
Pavel Pudlák
On Reducibility and Symmetry of Disjoint NP-Pairs. MFCS (2001)
Albert Atserias, Nicola Galesi, Pavel Pudlák
Monotone simulations of nonmonotone propositional proofs Electron. Colloquium Comput. Complex. 7 (87) (2000)
Pavel Pudlák, Russell Impagliazzo
-SAT (preliminary version). SODA (2000)
Bruno Codenotti, Pavel Pudlák, Giovanni Resta
Some structural properties of low-rank matrices related to computational complexity. Theor. Comput. Sci. 235 (1) (2000)
Pavel Pudlák
A note on the use of determinant for proving lower bounds on the size of linear circuits. Inf. Process. Lett. 74 (5-6) (2000)
Pavel Pudlák
Proofs as Games. Am. Math. Mon. 107 (6) (2000)
Ramamohan Paturi, Pavel Pudlák, Francis Zane
Satisfiability Coding Lemma. Chic. J. Theor. Comput. Sci. 1999 (1999)
Pavel Pudlák
A Note on Applicability of the Incompleteness Theorem to Human Mind. Ann. Pure Appl. Log. 96 (1-3) (1999)

Pavel Pudlák.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Pavel Pudlák