| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Pavel Pudlák, Neil Thapen |
Alternating minima and maxima, Nash equilibria and Bounded Arithmetic.  |
Ann. Pure Appl. Logic  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
A lower bound on the size of resolution proofs of the Ramsey theorem. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | 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. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák |
Pseudorandom generators for group products: extended abstract. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandr V. Kostochka, Pavel Pudlák, Vojtech Rödl |
Some constructive bounds on Ramsey numbers. |
J. Comb. Theory, Ser. B |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák |
Pseudorandom Generators for Group Products. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák |
On convex complexity measures. |
Theor. Comput. Sci. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
On extracting computations from propositional proofs (a survey). |
FSTTCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Ramamohan Paturi, Pavel Pudlák |
On the complexity of circuit satisfiability. |
STOC |
2010 |
DBLP DOI BibTeX RDF |
NP-completeness, circuit satisfiability |
| 1 | Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák |
On convex complexity measures. |
Electronic Colloquium on Computational Complexity (ECCC) |
2009 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák |
Quantum deduction rules. |
Ann. Pure Appl. Logic |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
Fragments of bounded arithmetic and the lengths of proofs. |
J. Symb. Log. |
2008 |
DBLP BibTeX RDF |
|
| 1 | Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane |
Backtracking Based k-SAT Algorithms. |
Encyclopedia of Algorithms |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
Twelve Problems in Proof Complexity. |
CSR |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Dmitry Gavinsky, Pavel Pudlák |
Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity. |
IEEE Conference on Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
separation of communication classes, communication complexity, quantum communication |
| 1 | Dmitry Gavinsky, Pavel Pudlák |
Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák |
Quantum deduction rules. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák |
Gödel and computations: a 100th anniversary retrospective. |
SIGACT News |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, Dieter van Melkebeek (eds.) |
Complexity of Boolean Functions, 12.03. - 17.03.2006 |
Complexity of Boolean Functions |
2006 |
DBLP BibTeX RDF |
|
| 1 | Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, Dieter van Melkebeek |
06111 Abstracts Collection -- Complexity of Boolean Functions. |
Complexity of Boolean Functions |
2006 |
DBLP BibTeX RDF |
|
| 1 | Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, Rüdiger Reischuk |
06111 Executive Summary -- Complexity of Boolean Functions. |
Complexity of Boolean Functions |
2006 |
DBLP BibTeX RDF |
|
| 1 | Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien |
Lower bounds for circuits with MOD_m gates. |
FOCS |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
Godel and Computations (Abstract). |
IEEE Conference on Computational Complexity |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
On Search Problems in Complexity Theory and in Logic (Abstract). |
CIAC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
A nonlinear bound on the number of wires in bounded depth circuits |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane |
An improved exponential-time algorithm for k-SAT. |
J. ACM |
2005 |
DBLP DOI BibTeX RDF |
CNF satisfiability, randomized algorithms |
| 1 | Michal Koucký, Pavel Pudlák, Denis Thérien |
Bounded-depth circuits: separating wires from gates. |
STOC |
2005 |
DBLP DOI BibTeX RDF |
communication, complexity, lower bounds, regular languages, wires, constant-depth circuits, gates |
| 1 | Ramamohan Paturi, Pavel Pudlák |
Circuit lower bounds and linear codes |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Anna Gál, Pavel Pudlák |
A note on monotone complexity and the rank of matrices. |
Inf. Process. Lett. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
On reducibility and symmetry of disjoint NP pairs. |
Theor. Comput. Sci. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
Parallel strategies. |
J. Symb. Log. |
2003 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák |
An Application of Hindman's Theorem to a Problem on Communication Complexity. |
Combinatorics, Probability & Computing |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
Monotone complexity and the rank of matrices |
Electronic Colloquium on Computational Complexity (ECCC) |
2002 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák |
Cycles of Nonzero Elements in Low Rank Matrices. |
Combinatorica |
2002 |
DBLP DOI BibTeX RDF |
AMS Subject Classification (1991) Classes: 05C99, 15A99, 68R10 |
| 1 | Albert Atserias, Nicola Galesi, Pavel Pudlák |
Monotone simulations of non-monotone proofs. |
J. Comput. Syst. Sci. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
On reducibility and symmetry of disjoint NP-pairs |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák |
Complexity Theory and Genetics: The Computational Power of Crossing Over. |
Inf. Comput. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Samuel R. Buss, Pavel Pudlák |
On the computational content of intuitionistic propositional proofs. |
Ann. Pure Appl. Logic |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
Gust Editor's Foreword. |
J. Comput. Syst. Sci. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
On Reducibility and Symmetry of Disjoint NP-Pairs. |
MFCS |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Albert Atserias, Nicola Galesi, Pavel Pudlák |
Monotone Simulations of Nonmonotone Proofs. (PDF / PS) |
IEEE Conference on Computational Complexity |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
A note on the use of determinant for proving lower bounds on the size of linear circuits. |
Inf. Process. Lett. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Albert Atserias, Nicola Galesi, Pavel Pudlák |
Monotone simulations of nonmonotone propositional proofs |
Electronic Colloquium on Computational Complexity (ECCC) |
2000 |
DBLP BibTeX RDF |
|
| 1 | Bruno Codenotti, Pavel Pudlák, Giovanni Resta |
Some structural properties of low-rank matrices related to computational complexity. |
Theor. Comput. Sci. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák, Russell Impagliazzo |
A lower bound for DLL algorithms for k-SAT (preliminary version). |
SODA |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Ramamohan Paturi, Pavel Pudlák, Francis Zane |
Satisfiability Coding Lemma. |
Chicago J. Theor. Comput. Sci. |
1999 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák |
A Note on Applicability of the Incompleteness Theorem to Human Mind. |
Ann. Pure Appl. Logic |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Russell Impagliazzo, Pavel Pudlák, Jiri Sgall |
Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm. |
Computational Complexity |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits |
Electronic Colloquium on Computational Complexity (ECCC) |
1998 |
DBLP BibTeX RDF |
|
| 1 | Jan Krajícek, Pavel Pudlák |
Some Consequences of Cryptographical Conjectures for S12 and EF. |
Inf. Comput. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthias Krause, Pavel Pudlák |
Computing Boolean Functions by Polynomials and Threshold Circuits. |
Computational Complexity |
1998 |
DBLP DOI BibTeX RDF |
Complexity of Boolean functions, circuit lower bounds, representations by multivariate polynomials, threshold circuits |
| 1 | Pavel Pudlák |
Satisfiability - Algorithms and Logic. |
MFCS |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane |
An Improved Exponential-Time Algorithm for k-SAT. |
FOCS |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Bruno Codenotti, Pavel Pudlák, Giovanni Resta |
Some structural properties of low rank matrices related to computational complexity |
Electronic Colloquium on Computational Complexity (ECCC) |
1997 |
DBLP BibTeX RDF |
|
| 1 | Russell Impagliazzo, Pavel Pudlák, Jiri Sgall |
Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm |
Electronic Colloquium on Computational Complexity (ECCC) |
1997 |
DBLP BibTeX RDF |
|
| 1 | Matthias Krause, Pavel Pudlák |
On the Computational Power of Depth-2 Circuits with Threshold and Modulo Gates. |
Theor. Comput. Sci. |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations. |
J. Symb. Log. |
1997 |
DBLP BibTeX RDF |
|
| 1 | Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jiri Sgall |
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. |
Computational Complexity |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák, Vojtech Rödl, Jiri Sgall |
Boolean Circuits, Tensor Ranks, and Communication Complexity. |
SIAM J. Comput. |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Hanno Lefmann, Pavel Pudlák, Petr Savický |
On Sparse Parity Check Matrices. |
Des. Codes Cryptography |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Ramamohan Paturi, Pavel Pudlák, Francis Zane |
Satisfiability Coding Lemma. |
FOCS |
1997 |
DBLP DOI BibTeX RDF |
satisfying assignments, satisfying assignment, Satisfiability Coding Lemma, computability, randomized algorithm, satisfiability, deterministic algorithm, conjunctive normal form, Boolean formulae |
| 1 | Hanno Lefmann, Pavel Pudlák, Petr Savický |
On Sparse Parity Chack Matrices (Extended Abstract). |
COCOON |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák, Jiri Sgall |
An Upper Bound for a Communication Game Related to Time-Space Tradeoffs |
Electronic Colloquium on Computational Complexity (ECCC) |
1995 |
DBLP BibTeX RDF |
|
| 1 | Jan Krajícek, Pavel Pudlák, Alan R. Woods |
An Exponenetioal Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle. |
Random Struct. Algorithms |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Stasys Jukna, Pavel Pudlák |
Top-Down Lower Bounds for Depth-Three Circuits. |
Computational Complexity |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthias Krause, Pavel Pudlák |
On Computing Boolean Functions by Sparse Real Polynomials. |
FOCS |
1995 |
DBLP DOI BibTeX RDF |
sparse real polynomials, threshold-parity circuits, threshold-and circuits, computational complexity, complexity, Boolean functions, Boolean functions, polynomials, polynomials |
| 1 | Matthias Krause, Pavel Pudlák |
On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates |
Electronic Colloquium on Computational Complexity (ECCC) |
1994 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák |
Complexity Theory and Genetics (extended abstract) |
Electronic Colloquium on Computational Complexity (ECCC) |
1994 |
DBLP BibTeX RDF |
|
| 1 | Jan Krajícek, Pavel Pudlák, Alan R. Woods |
An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle |
Electronic Colloquium on Computational Complexity (ECCC) |
1994 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák, Vojtech Rödl |
Some combinatorial-algebraic problems from complexity theory. |
Discrete Mathematics |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
Communication in Bounded Depth Circuits. |
Combinatorica |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Pavel Pudlák |
Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely). |
J. Comput. Syst. Sci. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan Krajícek, Pavel Pudlák |
Some Consequences of Cryptographical Conjectures for S_2^1 and EF. |
LCC |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
Unexpected Upper Bounds on the Complexity of Some Communication Games. |
ICALP |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák |
Lower Bound on Hilbert's Nullstellensatz and propositional proofs |
FOCS |
1994 |
DBLP DOI BibTeX RDF |
propositional formulas, Hilbert's Nullstellensatz, propositional proofs, modular counting principle, fixed cardinality, algebraic equations |
| 1 | Pavel Pudlák, Samuel R. Buss |
How to Lie Without Being (Easily) Convicted and the Length of Proofs in Propositional Calculus. |
CSL |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
Complexity Theory and Genetics. |
Structure in Complexity Theory Conference |
1994 |
DBLP BibTeX RDF |
|
| 1 | Matthias Krause, Pavel Pudlák |
On the computational power of depth 2 circuits with threshold and modulo gates. |
STOC |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán |
Threshold Circuits of Bounded Depth. |
J. Comput. Syst. Sci. |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
AC0 Circuit Complexity. |
FCT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Stasys Jukna, Pavel Pudlák |
Top-Down Lower Bounds for Depth 3 Circuits |
FOCS |
1993 |
DBLP DOI BibTeX RDF |
nonmonotone circuits, top-down lower bounds, depth 3 circuits, depth 3 AND-OR-NOT circuits, strong lower bound, top-down argument |
| 1 | Pavel Pudlák, Vojtech Rödl |
Modified ranks of tensors and the size of circuits. |
STOC |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák, Vojtech Rödl |
A combinatorial approach to complexity. |
Combinatorica |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, Alan R. Woods |
Exponential Lower Bounds for the Pigeonhole Principle |
STOC |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan Krajícek, Pavel Pudlák, Gaisi Takeuti |
Bounded Arithmetic and the Polynomial Hierarchy. |
Ann. Pure Appl. Logic |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | László Babai, Pavel Pudlák, Vojtech Rödl, Endre Szemerédi |
Lower Bounds to the Complexity of Symmetric Boolean Functions. |
Theor. Comput. Sci. |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan Krajícek, Pavel Pudlák, Jiri Sgall |
Interactive Computations of Optimal Solutions. |
MFCS |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
Ramsey's Theorem in Bounded Arithmetic. |
CSL |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan Krajícek, Pavel Pudlák |
Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations. |
J. Symb. Log. |
1989 |
DBLP BibTeX RDF |
|
| 1 | Pavol Duris, Pavel Pudlák |
On the Communication Complexity of Planarity. |
FCT |
1989 |
DBLP BibTeX RDF |
|
| 1 | Jan Krajícek, Pavel Pudlák |
Propositional Provability and Models of Weak Arithmetic. |
CSL |
1989 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák, Vojtech Rödl, Petr Savický |
Graph Complexity. |
Acta Inf. |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán |
Threshold circuits of bounded depth |
FOCS |
1987 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, László Babai, Péter Hajnal, János Komlós, Pavel Pudlák, Vojtech Rödl, Endre Szemerédi, György Turán |
Two lower bounds for branching programs |
STOC |
1986 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
Cuts, Consistency Statements and Interpretations. |
J. Symb. Log. |
1985 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák, Antonín Sochor |
Models of the Alternative Set Theory. |
J. Symb. Log. |
1984 |
DBLP BibTeX RDF |
|
| 1 | Jaroslav Morávek, Pavel Pudlák |
New Lower Bound for Polyhedral Membership Problem with an Application to Linear Programming. |
MFCS |
1984 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Pudlák |
A Lower Bound on Complexity of Branching Programs (Extended Abstract). |
MFCS |
1984 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")