| 2009 |
|---|
| 91 | EE | Pavel Pudlák:
Quantum deduction rules.
Ann. Pure Appl. Logic 157(1): 16-29 (2009) |
| 2008 |
|---|
| 90 | EE | Pavel Pudlák:
Twelve Problems in Proof Complexity.
CSR 2008: 13-27 |
| 89 | EE | Dmitry Gavinsky,
Pavel Pudlák:
Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity.
IEEE Conference on Computational Complexity 2008: 332-339 |
| 88 | EE | Ramamohan Paturi,
Pavel Pudlák,
Michael E. Saks,
Francis Zane:
Backtracking Based k-SAT Algorithms.
Encyclopedia of Algorithms 2008 |
| 2007 |
|---|
| 87 | EE | Pavel Pudlák:
Quantum deduction rules.
Electronic Colloquium on Computational Complexity (ECCC) 14(032): (2007) |
| 86 | EE | Dmitry Gavinsky,
Pavel Pudlák:
Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity.
Electronic Colloquium on Computational Complexity (ECCC) 14(074): (2007) |
| 2006 |
|---|
| 85 | | Matthias Krause,
Pavel Pudlák,
Rüdiger Reischuk,
Dieter van Melkebeek:
Complexity of Boolean Functions, 12.03. - 17.03.2006
Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2006 |
| 84 | EE | Pavel Pudlák:
On Search Problems in Complexity Theory and in Logic (Abstract).
CIAC 2006: 5 |
| 83 | EE | Matthias Krause,
Pavel Pudlák,
Rüdiger Reischuk,
Dieter van Melkebeek:
06111 Abstracts Collection -- Complexity of Boolean Functions.
Complexity of Boolean Functions 2006 |
| 82 | EE | Matthias Krause,
Dieter van Melkebeek,
Pavel Pudlák,
Rüdiger Reischuk:
06111 Executive Summary -- Complexity of Boolean Functions.
Complexity of Boolean Functions 2006 |
| 81 | EE | Arkadev Chattopadhyay,
Navin Goyal,
Pavel Pudlák,
Denis Thérien:
Lower bounds for circuits with MOD_m gates.
FOCS 2006: 709-718 |
| 80 | EE | Pavel Pudlák:
Godel and Computations (Abstract).
IEEE Conference on Computational Complexity 2006: 3-5 |
| 79 | EE | Pavel Pudlák:
Gödel and computations: a 100th anniversary retrospective.
SIGACT News 37(4): 13-21 (2006) |
| 2005 |
|---|
| 78 | EE | Michal Koucký,
Pavel Pudlák,
Denis Thérien:
Bounded-depth circuits: separating wires from gates.
STOC 2005: 257-265 |
| 77 | EE | Pavel Pudlák:
A nonlinear bound on the number of wires in bounded depth circuits
Electronic Colloquium on Computational Complexity (ECCC)(122): (2005) |
| 76 | EE | Ramamohan Paturi,
Pavel Pudlák,
Michael E. Saks,
Francis Zane:
An improved exponential-time algorithm for k-SAT.
J. ACM 52(3): 337-364 (2005) |
| 2004 |
|---|
| 75 | EE | Ramamohan Paturi,
Pavel Pudlák:
Circuit lower bounds and linear codes
Electronic Colloquium on Computational Complexity (ECCC)(004): (2004) |
| 2003 |
|---|
| 74 | | Pavel Pudlák:
An Application of Hindman's Theorem to a Problem on Communication Complexity.
Combinatorics, Probability & Computing 12(5-6): 661-670 (2003) |
| 73 | EE | Anna Gál,
Pavel Pudlák:
A note on monotone complexity and the rank of matrices.
Inf. Process. Lett. 87(6): 321-326 (2003) |
| 72 | EE | 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): 257 (2003) |
| 71 | EE | Pavel Pudlák:
On reducibility and symmetry of disjoint NP pairs.
Theor. Comput. Sci. 295: 323-339 (2003) |
| 2002 |
|---|
| 70 | EE | Pavel Pudlák:
Cycles of Nonzero Elements in Low Rank Matrices.
Combinatorica 22(2): 321-334 (2002) |
| 69 | EE | Pavel Pudlák:
Monotone complexity and the rank of matrices
Electronic Colloquium on Computational Complexity (ECCC)(007): (2002) |
| 68 | EE | Albert Atserias,
Nicola Galesi,
Pavel Pudlák:
Monotone simulations of non-monotone proofs.
J. Comput. Syst. Sci. 65(4): 626-638 (2002) |
| 2001 |
|---|
| 67 | EE | Albert Atserias,
Nicola Galesi,
Pavel Pudlák:
Monotone Simulations of Nonmonotone Proofs.
IEEE Conference on Computational Complexity 2001: 36-41 |
| 66 | EE | Pavel Pudlák:
On Reducibility and Symmetry of Disjoint NP-Pairs.
MFCS 2001: 621-632 |
| 65 | | Samuel R. Buss,
Pavel Pudlák:
On the computational content of intuitionistic propositional proofs.
Ann. Pure Appl. Logic 109(1-2): 49-63 (2001) |
| 64 | EE | Pavel Pudlák:
On reducibility and symmetry of disjoint NP-pairs
Electronic Colloquium on Computational Complexity (ECCC) 8(44): (2001) |
| 63 | EE | Pavel Pudlák:
Complexity Theory and Genetics: The Computational Power of Crossing Over.
Inf. Comput. 171(2): 201-223 (2001) |
| 62 | | Pavel Pudlák:
Gust Editor's Foreword.
J. Comput. Syst. Sci. 63(2): 147 (2001) |
| 2000 |
|---|
| 61 | EE | Pavel Pudlák,
Russell Impagliazzo:
A lower bound for DLL algorithms for k-SAT (preliminary version).
SODA 2000: 128-136 |
| 60 | EE | Albert Atserias,
Nicola Galesi,
Pavel Pudlák:
Monotone simulations of nonmonotone propositional proofs
Electronic Colloquium on Computational Complexity (ECCC) 7(87): (2000) |
| 59 | EE | 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): 197-201 (2000) |
| 58 | EE | Bruno Codenotti,
Pavel Pudlák,
Giovanni Resta:
Some structural properties of low-rank matrices related to computational complexity.
Theor. Comput. Sci. 235(1): 89-107 (2000) |
| 1999 |
|---|
| 57 | | Pavel Pudlák:
A Note on Applicability of the Incompleteness Theorem to Human Mind.
Ann. Pure Appl. Logic 96(1-3): 335-342 (1999) |
| 56 | EE | Ramamohan Paturi,
Pavel Pudlák,
Francis Zane:
Satisfiability Coding Lemma.
Chicago J. Theor. Comput. Sci. 1999: (1999) |
| 55 | | Russell Impagliazzo,
Pavel Pudlák,
Jiri Sgall:
Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm.
Computational Complexity 8(2): 127-144 (1999) |
| 1998 |
|---|
| 54 | EE | Ramamohan Paturi,
Pavel Pudlák,
Michael E. Saks,
Francis Zane:
An Improved Exponential-Time Algorithm for k-SAT.
FOCS 1998: 628-637 |
| 53 | EE | Pavel Pudlák:
Satisfiability - Algorithms and Logic.
MFCS 1998: 129-141 |
| 52 | EE | Matthias Krause,
Pavel Pudlák:
Computing Boolean Functions by Polynomials and Threshold Circuits.
Computational Complexity 7(4): 346-370 (1998) |
| 51 | EE | 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) 5(42): (1998) |
| 50 | | Jan Krajícek,
Pavel Pudlák:
Some Consequences of Cryptographical Conjectures for S12 and EF.
Inf. Comput. 140(1): 82-94 (1998) |
| 1997 |
|---|
| 49 | EE | Ramamohan Paturi,
Pavel Pudlák,
Francis Zane:
Satisfiability Coding Lemma.
FOCS 1997: 566-574 |
| 48 | | 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 6(3): 256-298 (1997) |
| 47 | | Hanno Lefmann,
Pavel Pudlák,
Petr Savický:
On Sparse Parity Check Matrices.
Des. Codes Cryptography 12(2): 107-130 (1997) |
| 46 | EE | Russell Impagliazzo,
Pavel Pudlák,
Jiri Sgall:
Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm
Electronic Colloquium on Computational Complexity (ECCC) 4(42): (1997) |
| 45 | EE | Bruno Codenotti,
Pavel Pudlák,
Giovanni Resta:
Some structural properties of low rank matrices related to computational complexity
Electronic Colloquium on Computational Complexity (ECCC) 4(43): (1997) |
| 44 | | Pavel Pudlák:
Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations.
J. Symb. Log. 62(3): 981-998 (1997) |
| 43 | | Pavel Pudlák,
Vojtech Rödl,
Jiri Sgall:
Boolean Circuits, Tensor Ranks, and Communication Complexity.
SIAM J. Comput. 26(3): 605-633 (1997) |
| 42 | EE | Matthias Krause,
Pavel Pudlák:
On the Computational Power of Depth-2 Circuits with Threshold and Modulo Gates.
Theor. Comput. Sci. 174(1-2): 137-156 (1997) |
| 1996 |
|---|
| 41 | | Hanno Lefmann,
Pavel Pudlák,
Petr Savický:
On Sparse Parity Chack Matrices (Extended Abstract).
COCOON 1996: 41-49 |
| 1995 |
|---|
| 40 | | Matthias Krause,
Pavel Pudlák:
On Computing Boolean Functions by Sparse Real Polynomials.
FOCS 1995: 682-691 |
| 39 | | Johan Håstad,
Stasys Jukna,
Pavel Pudlák:
Top-Down Lower Bounds for Depth-Three Circuits.
Computational Complexity 5(2): 99-112 (1995) |
| 38 | EE | Pavel Pudlák,
Jiri Sgall:
An Upper Bound for a Communication Game Related to Time-Space Tradeoffs
Electronic Colloquium on Computational Complexity (ECCC) 2(10): (1995) |
| 37 | | 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 7(1): 15-40 (1995) |
| 1994 |
|---|
| 36 | | Pavel Pudlák,
Samuel R. Buss:
How to Lie Without Being (Easily) Convicted and the Length of Proofs in Propositional Calculus.
CSL 1994: 151-162 |
| 35 | | Paul Beame,
Russell Impagliazzo,
Jan Krajícek,
Toniann Pitassi,
Pavel Pudlák:
Lower Bound on Hilbert's Nullstellensatz and propositional proofs
FOCS 1994: 794-806 |
| 34 | | Pavel Pudlák:
Unexpected Upper Bounds on the Complexity of Some Communication Games.
ICALP 1994: 1-10 |
| 33 | | Jan Krajícek,
Pavel Pudlák:
Some Consequences of Cryptographical Conjectures for S_2^1 and EF.
LCC 1994: 210-220 |
| 32 | EE | Matthias Krause,
Pavel Pudlák:
On the computational power of depth 2 circuits with threshold and modulo gates.
STOC 1994: 48-57 |
| 31 | | Pavel Pudlák:
Complexity Theory and Genetics.
Structure in Complexity Theory Conference 1994: 383-395 |
| 30 | | Pavel Pudlák:
Communication in Bounded Depth Circuits.
Combinatorica 14(2): 203-216 (1994) |
| 29 | EE | Pavel Pudlák,
Vojtech Rödl:
Some combinatorial-algebraic problems from complexity theory.
Discrete Mathematics 136(1-3): 253-279 (1994) |
| 28 | EE | Pavel Pudlák:
Complexity Theory and Genetics (extended abstract)
Electronic Colloquium on Computational Complexity (ECCC) 1(13): (1994) |
| 27 | EE | 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) 1(18): (1994) |
| 26 | EE | Matthias Krause,
Pavel Pudlák:
On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates
Electronic Colloquium on Computational Complexity (ECCC) 1(23): (1994) |
| 25 | | Noga Alon,
Pavel Pudlák:
Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely).
J. Comput. Syst. Sci. 48(1): 194-202 (1994) |
| 1993 |
|---|
| 24 | | Pavel Pudlák:
AC0 Circuit Complexity.
FCT 1993: 106-120 |
| 23 | | Johan Håstad,
Stasys Jukna,
Pavel Pudlák:
Top-Down Lower Bounds for Depth 3 Circuits
FOCS 1993: 124-129 |
| 22 | EE | Pavel Pudlák,
Vojtech Rödl:
Modified ranks of tensors and the size of circuits.
STOC 1993: 523-531 |
| 21 | | András Hajnal,
Wolfgang Maass,
Pavel Pudlák,
Mario Szegedy,
György Turán:
Threshold Circuits of Bounded Depth.
J. Comput. Syst. Sci. 46(2): 129-154 (1993) |
| 1992 |
|---|
| 20 | | Paul Beame,
Russell Impagliazzo,
Jan Krajícek,
Toniann Pitassi,
Pavel Pudlák,
Alan R. Woods:
Exponential Lower Bounds for the Pigeonhole Principle
STOC 1992: 200-220 |
| 19 | | Pavel Pudlák,
Vojtech Rödl:
A combinatorial approach to complexity.
Combinatorica 12(2): 221-226 (1992) |
| 1991 |
|---|
| 18 | | Jan Krajícek,
Pavel Pudlák,
Gaisi Takeuti:
Bounded Arithmetic and the Polynomial Hierarchy.
Ann. Pure Appl. Logic 52(1-2): 143-153 (1991) |
| 1990 |
|---|
| 17 | | Pavel Pudlák:
Ramsey's Theorem in Bounded Arithmetic.
CSL 1990: 308-317 |
| 16 | | Jan Krajícek,
Pavel Pudlák,
Jiri Sgall:
Interactive Computations of Optimal Solutions.
MFCS 1990: 48-60 |
| 15 | | László Babai,
Pavel Pudlák,
Vojtech Rödl,
Endre Szemerédi:
Lower Bounds to the Complexity of Symmetric Boolean Functions.
Theor. Comput. Sci. 74(3): 313-323 (1990) |
| 1989 |
|---|
| 14 | | Jan Krajícek,
Pavel Pudlák:
Propositional Provability and Models of Weak Arithmetic.
CSL 1989: 193-210 |
| 13 | | Pavol Duris,
Pavel Pudlák:
On the Communication Complexity of Planarity.
FCT 1989: 145-147 |
| 12 | | Jan Krajícek,
Pavel Pudlák:
Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations.
J. Symb. Log. 54(3): 1063-1079 (1989) |
| 1988 |
|---|
| 11 | | Pavel Pudlák,
Vojtech Rödl,
Petr Savický:
Graph Complexity.
Acta Inf. 25(5): 515-535 (1988) |
| 1987 |
|---|
| 10 | | András Hajnal,
Wolfgang Maass,
Pavel Pudlák,
Mario Szegedy,
György Turán:
Threshold circuits of bounded depth
FOCS 1987: 99-110 |
| 1986 |
|---|
| 9 | | 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: 30-38 |
| 1985 |
|---|
| 8 | | Pavel Pudlák:
Cuts, Consistency Statements and Interpretations.
J. Symb. Log. 50(2): 423-441 (1985) |
| 1984 |
|---|
| 7 | | Jaroslav Morávek,
Pavel Pudlák:
New Lower Bound for Polyhedral Membership Problem with an Application to Linear Programming.
MFCS 1984: 416-424 |
| 6 | | Pavel Pudlák:
A Lower Bound on Complexity of Branching Programs (Extended Abstract).
MFCS 1984: 480-489 |
| 5 | | Pavel Pudlák,
Antonín Sochor:
Models of the Alternative Set Theory.
J. Symb. Log. 49(2): 570-585 (1984) |
| 1983 |
|---|
| 4 | | Pavel Pudlák:
Bounds for Hodes-Specker theorem.
Logic and Machines 1983: 421-445 |
| 1982 |
|---|
| 3 | EE | Pavel Pudlák,
Vojtech Rödl:
Partition theorems for systems of finite subsets of integers.
Discrete Mathematics 39(1): 67-73 (1982) |
| 1979 |
|---|
| 2 | | Pavel Pudlák,
Frederick N. Springsteel:
Complexity in Mechanized Hypothesis Formation.
Theor. Comput. Sci. 8: 203-225 (1979) |
| 1975 |
|---|
| 1 | | Pavel Pudlák:
Polynomially Complete Problems in the Logic of Automated Discovery.
MFCS 1975: 358-361 |
