dblp.uni-trier.dewww.uni-trier.de

Pavel Pudlák Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

*2009
91EEPavel Pudlák: Quantum deduction rules. Ann. Pure Appl. Logic 157(1): 16-29 (2009)
2008
90EEPavel Pudlák: Twelve Problems in Proof Complexity. CSR 2008: 13-27
89EEDmitry Gavinsky, Pavel Pudlák: Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity. IEEE Conference on Computational Complexity 2008: 332-339
88EERamamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane: Backtracking Based k-SAT Algorithms. Encyclopedia of Algorithms 2008
2007
87EEPavel Pudlák: Quantum deduction rules. Electronic Colloquium on Computational Complexity (ECCC) 14(032): (2007)
86EEDmitry 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
84EEPavel Pudlák: On Search Problems in Complexity Theory and in Logic (Abstract). CIAC 2006: 5
83EEMatthias Krause, Pavel Pudlák, Rüdiger Reischuk, Dieter van Melkebeek: 06111 Abstracts Collection -- Complexity of Boolean Functions. Complexity of Boolean Functions 2006
82EEMatthias Krause, Dieter van Melkebeek, Pavel Pudlák, Rüdiger Reischuk: 06111 Executive Summary -- Complexity of Boolean Functions. Complexity of Boolean Functions 2006
81EEArkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien: Lower bounds for circuits with MOD_m gates. FOCS 2006: 709-718
80EEPavel Pudlák: Godel and Computations (Abstract). IEEE Conference on Computational Complexity 2006: 3-5
79EEPavel Pudlák: Gödel and computations: a 100th anniversary retrospective. SIGACT News 37(4): 13-21 (2006)
2005
78EEMichal Koucký, Pavel Pudlák, Denis Thérien: Bounded-depth circuits: separating wires from gates. STOC 2005: 257-265
77EEPavel Pudlák: A nonlinear bound on the number of wires in bounded depth circuits Electronic Colloquium on Computational Complexity (ECCC)(122): (2005)
76EERamamohan 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
75EERamamohan 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)
73EEAnna Gál, Pavel Pudlák: A note on monotone complexity and the rank of matrices. Inf. Process. Lett. 87(6): 321-326 (2003)
72EEAnna 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)
71EEPavel Pudlák: On reducibility and symmetry of disjoint NP pairs. Theor. Comput. Sci. 295: 323-339 (2003)
2002
70EEPavel Pudlák: Cycles of Nonzero Elements in Low Rank Matrices. Combinatorica 22(2): 321-334 (2002)
69EEPavel Pudlák: Monotone complexity and the rank of matrices Electronic Colloquium on Computational Complexity (ECCC)(007): (2002)
68EEAlbert Atserias, Nicola Galesi, Pavel Pudlák: Monotone simulations of non-monotone proofs. J. Comput. Syst. Sci. 65(4): 626-638 (2002)
2001
67EEAlbert Atserias, Nicola Galesi, Pavel Pudlák: Monotone Simulations of Nonmonotone Proofs. IEEE Conference on Computational Complexity 2001: 36-41
66EEPavel 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)
64EEPavel Pudlák: On reducibility and symmetry of disjoint NP-pairs Electronic Colloquium on Computational Complexity (ECCC) 8(44): (2001)
63EEPavel 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
61EEPavel Pudlák, Russell Impagliazzo: A lower bound for DLL algorithms for k-SAT (preliminary version). SODA 2000: 128-136
60EEAlbert Atserias, Nicola Galesi, Pavel Pudlák: Monotone simulations of nonmonotone propositional proofs Electronic Colloquium on Computational Complexity (ECCC) 7(87): (2000)
59EEPavel 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)
58EEBruno 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)
56EERamamohan 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
54EERamamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane: An Improved Exponential-Time Algorithm for k-SAT. FOCS 1998: 628-637
53EEPavel Pudlák: Satisfiability - Algorithms and Logic. MFCS 1998: 129-141
52EEMatthias Krause, Pavel Pudlák: Computing Boolean Functions by Polynomials and Threshold Circuits. Computational Complexity 7(4): 346-370 (1998)
51EEPavel 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
49EERamamohan 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)
46EERussell 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)
45EEBruno 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)
42EEMatthias 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)
38EEPavel 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
36EEPavel 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
34EEPavel 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
32EEMatthias 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)
29EEPavel Pudlák, Vojtech Rödl: Some combinatorial-algebraic problems from complexity theory. Discrete Mathematics 136(1-3): 253-279 (1994)
28EEPavel Pudlák: Complexity Theory and Genetics (extended abstract) Electronic Colloquium on Computational Complexity (ECCC) 1(13): (1994)
27EEJan 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)
26EEMatthias 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
22EEPavel 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
17EEPavel Pudlák: Ramsey's Theorem in Bounded Arithmetic. CSL 1990: 308-317
16EEJan 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
14EEJan 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
7EEJaroslav Morávek, Pavel Pudlák: New Lower Bound for Polyhedral Membership Problem with an Application to Linear Programming. MFCS 1984: 416-424
6EEPavel 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
3EEPavel 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
1EEPavel Pudlák: Polynomially Complete Problems in the Logic of Automated Discovery. MFCS 1975: 358-361

Coauthor Index

1Miklós Ajtai [9]
2Noga Alon [25]
3Albert Atserias [60] [67] [68]
4László Babai [9] [15]
5Paul Beame [20] [35]
6Samuel R. Buss [36] [48] [65]
7Arkadev Chattopadhyay [81]
8Bruno Codenotti [45] [58]
9Pavol Duris [13]
10Anna Gál [72] [73]
11Nicola Galesi [60] [67] [68]
12Dmitry Gavinsky [86] [89]
13Navin Goyal [81]
14András Hajnal [10] [21]
15Péter Hajnal [9]
16Johan Håstad [23] [39]
17Russell Impagliazzo [20] [35] [46] [48] [55] [61]
18Stasys Jukna [23] [39]
19János Komlós [9]
20Michal Koucký [78]
21Jan Krajícek [12] [14] [16] [18] [20] [27] [33] [35] [37] [48] [50]
22Matthias Krause [26] [32] [40] [42] [52] [82] [83] [85]
23Hanno Lefmann [41] [47]
24Wolfgang Maass [10] [21]
25Dieter van Melkebeek [82] [83] [85]
26Jaroslav Morávek [7]
27Ramamohan Paturi [49] [54] [56] [75] [76] [88]
28Toniann Pitassi [20] [35]
29Alexander A. Razborov [48]
30Rüdiger Reischuk [82] [83] [85]
31Giovanni Resta [45] [58]
32Vojtech Rödl [3] [9] [11] [15] [19] [22] [29] [43]
33Michael E. Saks [54] [76] [88]
34Petr Savický [11] [41] [47]
35Jiri Sgall [16] [38] [43] [46] [48] [55]
36Antonín Sochor [5]
37Frederick N. Springsteel [2]
38Mario Szegedy [10] [21]
39Endre Szemerédi [9] [15]
40Gaisi Takeuti [18]
41Denis Thérien [78] [81]
42György Turán [9] [10] [21]
43Alan R. Woods [20] [27] [37]
44Francis Zane [49] [54] [56] [76] [88]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)