Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Pavel Pudlák
2010 – today
- 2013
[j47]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 Transactions on Information Theory 59(10): 6611-6627 (2013)- [c42]Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen: The Complexity of Proving That a Graph Is Ramsey. ICALP (1) 2013: 684-695
- [c41]Arnold Beckmann, Pavel Pudlák, Neil Thapen: Parity Games and Propositional Proofs. MFCS 2013: 111-122
- [i20]Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen: The complexity of proving that a graph is Ramsey. CoRR abs/1303.3166 (2013)
- [i19]Massimo Lauria, Pavel Pudlák, Vojtech Rödl, Neil Thapen: The complexity of proving that a graph is Ramsey. Electronic Colloquium on Computational Complexity (ECCC) 20: 38 (2013)
- [i18]Pavel Pudlák, Arnold Beckmann, Neil Thapen: Parity Games and Propositional Proofs. Electronic Colloquium on Computational Complexity (ECCC) 20: 92 (2013)
- 2012
- [j46]Pavel Pudlák, Neil Thapen: Alternating minima and maxima, Nash equilibria and Bounded Arithmetic. Ann. Pure Appl. Logic 163(5): 604-614 (2012)
- [j45]Pavel Pudlák: A lower bound on the size of resolution proofs of the Ramsey theorem. Inf. Process. Lett. 112(14-15): 610-611 (2012)
- [c40]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: 479-494
- 2011
- [j44]Pavel Pudlák: A lower bound on the size of resolution proofs of the Ramsey theorem. Electronic Colloquium on Computational Complexity (ECCC) 18: 162 (2011)
- [c39]Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák: Pseudorandom generators for group products: extended abstract. STOC 2011: 263-272
- [i17]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) 18: 150 (2011)
- 2010
- [j43]Alexandr V. Kostochka, Pavel Pudlák, Vojtech Rödl: Some constructive bounds on Ramsey numbers. J. Comb. Theory, Ser. B 100(5): 439-445 (2010)
- [j42]Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák: On convex complexity measures. Theor. Comput. Sci. 411(16-18): 1842-1854 (2010)
- [c38]
- [c37]
- [i16]Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák: Pseudorandom Generators for Group Products. Electronic Colloquium on Computational Complexity (ECCC) 17: 113 (2010)
2000 – 2009
- 2009
- [j41]
- [i15]Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák: On convex complexity measures. Electronic Colloquium on Computational Complexity (ECCC) 16: 40 (2009)
- 2008
- [j40]Pavel Pudlák: Fragments of bounded arithmetic and the lengths of proofs. J. Symb. Log. 73(4): 1389-1406 (2008)
- [c36]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
- [c35]
- [r1]Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane: Backtracking Based k-SAT Algorithms. Encyclopedia of Algorithms 2008
- 2007
- [i14]Pavel Pudlák: Quantum deduction rules. Electronic Colloquium on Computational Complexity (ECCC) 14(032) (2007)
- [i13]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
- [j39]Pavel Pudlák: Gödel and computations: a 100th anniversary retrospective. SIGACT News 37(4): 13-21 (2006)
- [c34]
- [c33]Pavel Pudlák: Godel and Computations (Abstract). IEEE Conference on Computational Complexity 2006: 3-5
- [c32]Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, Rüdiger Reischuk: 06111 Executive Summary -- Complexity of Boolean Functions. Complexity of Boolean Functions 2006
- [c31]Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, Dieter van Melkebeek: 06111 Abstracts Collection -- Complexity of Boolean Functions. Complexity of Boolean Functions 2006
- [c30]Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien: Lower bounds for circuits with MOD_m gates. FOCS 2006: 709-718
- [e1]Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, Dieter van Melkebeek (Eds.): Complexity of Boolean Functions, 12.03. - 17.03.2006. Dagstuhl Seminar Proceedings 06111, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2006
- 2005
- [j38]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)
- [c29]Michal Koucký, Pavel Pudlák, Denis Thérien: Bounded-depth circuits: separating wires from gates. STOC 2005: 257-265
- [i12]Pavel Pudlák: A nonlinear bound on the number of wires in bounded depth circuits. Electronic Colloquium on Computational Complexity (ECCC)(122) (2005)
- 2004
- [i11]Ramamohan Paturi, Pavel Pudlák: Circuit lower bounds and linear codes. Electronic Colloquium on Computational Complexity (ECCC)(004) (2004)
- 2003
- [j37]Pavel Pudlák: An Application of Hindman's Theorem to a Problem on Communication Complexity. Combinatorics, Probability & Computing 12(5-6): 661-670 (2003)
- [j36]Anna Gál, Pavel Pudlák: A note on monotone complexity and the rank of matrices. Inf. Process. Lett. 87(6): 321-326 (2003)
- [j35]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)
- [j34]
- [j33]Pavel Pudlák: On reducibility and symmetry of disjoint NP pairs. Theor. Comput. Sci. 295: 323-339 (2003)
- 2002
- [j32]
- [j31]Albert Atserias, Nicola Galesi, Pavel Pudlák: Monotone simulations of non-monotone proofs. J. Comput. Syst. Sci. 65(4): 626-638 (2002)
- [i10]Pavel Pudlák: Monotone complexity and the rank of matrices. Electronic Colloquium on Computational Complexity (ECCC)(007) (2002)
- 2001
- [j30]Samuel R. Buss, Pavel Pudlák: On the computational content of intuitionistic propositional proofs. Ann. Pure Appl. Logic 109(1-2): 49-63 (2001)
- [j29]Pavel Pudlák: Complexity Theory and Genetics: The Computational Power of Crossing Over. Inf. Comput. 171(2): 201-223 (2001)
- [j28]
- [c28]Albert Atserias, Nicola Galesi, Pavel Pudlák: Monotone Simulations of Nonmonotone Proofs. IEEE Conference on Computational Complexity 2001: 36-41
- [c27]
- [i9]Pavel Pudlák: On reducibility and symmetry of disjoint NP-pairs. Electronic Colloquium on Computational Complexity (ECCC) 8(44) (2001)
- 2000
- [j27]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)
- [j26]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)
- [c26]Pavel Pudlák, Russell Impagliazzo: A lower bound for DLL algorithms for k-SAT (preliminary version). SODA 2000: 128-136
- [i8]Albert Atserias, Nicola Galesi, Pavel Pudlák: Monotone simulations of nonmonotone propositional proofs. Electronic Colloquium on Computational Complexity (ECCC) 7(87) (2000)
1990 – 1999
- 1999
- [j25]Pavel Pudlák: A Note on Applicability of the Incompleteness Theorem to Human Mind. Ann. Pure Appl. Logic 96(1-3): 335-342 (1999)
- [j24]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)
- [j23]Ramamohan Paturi, Pavel Pudlák, Francis Zane: Satisfiability Coding Lemma. Chicago J. Theor. Comput. Sci. 1999 (1999)
- 1998
- [j22]Matthias Krause, Pavel Pudlák: Computing Boolean Functions by Polynomials and Threshold Circuits. Computational Complexity 7(4): 346-370 (1998)
- [j21]Jan Krajícek, Pavel Pudlák: Some Consequences of Cryptographical Conjectures for S12 and EF. Inf. Comput. 140(1): 82-94 (1998)
- [c25]Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane: An Improved Exponential-Time Algorithm for k-SAT. FOCS 1998: 628-637
- [c24]
- [i7]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)
- 1997
- [j20]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)
- [j19]Hanno Lefmann, Pavel Pudlák, Petr Savický: On Sparse Parity Check Matrices. Des. Codes Cryptography 12(2): 107-130 (1997)
- [j18]Pavel Pudlák: Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations. J. Symb. Log. 62(3): 981-998 (1997)
- [j17]Pavel Pudlák, Vojtech Rödl, Jiri Sgall: Boolean Circuits, Tensor Ranks, and Communication Complexity. SIAM J. Comput. 26(3): 605-633 (1997)
- [j16]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)
- [c23]
- [i6]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)
- [i5]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)
- 1996
- [c22]Hanno Lefmann, Pavel Pudlák, Petr Savický: On Sparse Parity Chack Matrices (Extended Abstract). COCOON 1996: 41-49
- 1995
- [j15]Johan Håstad, Stasys Jukna, Pavel Pudlák: Top-Down Lower Bounds for Depth-Three Circuits. Computational Complexity 5(2): 99-112 (1995)
- [j14]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)
- [c21]Matthias Krause, Pavel Pudlák: On Computing Boolean Functions by Sparse Real Polynomials. FOCS 1995: 682-691
- [i4]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)
- 1994
- [j13]
- [j12]Pavel Pudlák, Vojtech Rödl: Some combinatorial-algebraic problems from complexity theory. Discrete Mathematics 136(1-3): 253-279 (1994)
- [j11]Noga Alon, Pavel Pudlák: Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely). J. Comput. Syst. Sci. 48(1): 194-202 (1994)
- [c20]Pavel Pudlák: Complexity Theory and Genetics. Structure in Complexity Theory Conference 1994: 383-395
- [c19]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
- [c18]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
- [c17]Pavel Pudlák: Unexpected Upper Bounds on the Complexity of Some Communication Games. ICALP 1994: 1-10
- [c16]Jan Krajícek, Pavel Pudlák: Some Consequences of Cryptographical Conjectures for S_2^1 and EF. LCC 1994: 210-220
- [c15]Matthias Krause, Pavel Pudlák: On the computational power of depth 2 circuits with threshold and modulo gates. STOC 1994: 48-57
- [i3]Pavel Pudlák: Complexity Theory and Genetics (extended abstract). Electronic Colloquium on Computational Complexity (ECCC) 1(13) (1994)
- [i2]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)
- [i1]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)
- 1993
- [j10]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)
- [c14]
- [c13]Johan Håstad, Stasys Jukna, Pavel Pudlák: Top-Down Lower Bounds for Depth 3 Circuits. FOCS 1993: 124-129
- [c12]
- 1992
- [j9]Pavel Pudlák, Vojtech Rödl: A combinatorial approach to complexity. Combinatorica 12(2): 221-226 (1992)
- [c11]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
- 1991
- [j8]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
- [j7]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)
- [c10]
- [c9]Jan Krajícek, Pavel Pudlák, Jiri Sgall: Interactive Computations of Optimal Solutions. MFCS 1990: 48-60
1980 – 1989
- 1989
- [j6]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)
- [c8]Jan Krajícek, Pavel Pudlák: Propositional Provability and Models of Weak Arithmetic. CSL 1989: 193-210
- [c7]
- 1988
- [j5]
- 1987
- [c6]András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán: Threshold circuits of bounded depth. FOCS 1987: 99-110
- 1986
- [c5]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
- [j4]
- 1984
- [j3]Pavel Pudlák, Antonín Sochor: Models of the Alternative Set Theory. J. Symb. Log. 49(2): 570-585 (1984)
- [c4]Jaroslav Morávek, Pavel Pudlák: New Lower Bound for Polyhedral Membership Problem with an Application to Linear Programming. MFCS 1984: 416-424
- [c3]Pavel Pudlák: A Lower Bound on Complexity of Branching Programs (Extended Abstract). MFCS 1984: 480-489
- 1983
- [c2]
- 1982
- [j2]Pavel Pudlák, Vojtech Rödl: Partition theorems for systems of finite subsets of integers. Discrete Mathematics 39(1): 67-73 (1982)
1970 – 1979
- 1979
- [j1]Pavel Pudlák, Frederick N. Springsteel: Complexity in Mechanized Hypothesis Formation. Theor. Comput. Sci. 8: 203-225 (1979)
- 1975
- [c1]Pavel Pudlák: Polynomially Complete Problems in the Logic of Automated Discovery. MFCS 1975: 358-361
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-10-02 11:05 CEST by the dblp team