## Pudlák, Pavel

Compute Distance To:
 Author ID: pudlak.pavel Published as: Pudlák, Pavel; Pudlák, P.; Pudlak, Pavel; Pudlák, Petr; Pudlak, P. Homepage: http://users.math.cas.cz/~pudlak/
 Documents Indexed: 153 Publications since 1975, including 7 Books 2 Contributions as Editor Co-Authors: 78 Co-Authors with 96 Joint Publications 2,654 Co-Co-Authors
all top 5

### Co-Authors

 59 single-authored 11 Krajíček, Jan 11 Rodl, Vojtech 8 Thapen, Neil 6 Hájek, Petr 6 Sgall, Jiří 5 Paturi, Ramamohan 5 Tůma, Jiří 4 Gavinsky, Dmitry 4 Impagliazzo, Russell 4 Koucký, Michal 4 Krause, Matthias 3 Alon, Noga M. 3 Buss, Samuel R. 3 Gál, Anna 3 Savický, Petr 2 Beckmann, Arnold 2 De Oliveira Oliveira, Mateus 2 Galesi, Nicola 2 Hansen, Kristoffer Arnsfelt 2 Hora, Jan 2 Hrubeš, Pavel 2 Kowalski, Oldřich 2 Křížek, Michal 2 Lauria, Massimo 2 Markl, Martin 2 Sochor, Antonin 2 Somer, Lawrence E. 2 Sutcliffe, Geoff 2 Viola, Emanuele 2 Vrkoč, Ivo 2 Yukna, Stasys P. 2 Zane, Francis X. 1 Atserias, Albert 1 Baaz, Matthias 1 Babai, László 1 Beame, Paul W. 1 Čačić, Vedran 1 Codenotti, Bruno 1 Ďuriš, Pavol 1 Glivický, Petr 1 Hajnal, András 1 Håstad, Johan Torkel 1 Ježek, Jaroslav 1 Kostochka, Aleksandr Vasil’evich 1 Kreisel, Georg 1 Kulikov, Alexander S. 1 Lefmann, Hanno 1 Lokshtanov, Daniel 1 Maass, Wolfgang 1 Mikhailin, Ivan 1 Montagna, Franco 1 Moravek, Jaroslav 1 Mycielski, Jan 1 Nešetřil, Jaroslav 1 Nimbhorkar, Prajakta 1 Pálfy, Péter Pál 1 Pitassi, Toniann 1 Poljak, Svatopluk 1 Rabe, Florian 1 Razborov, Aleksandr Aleksandrovich 1 Resta, Giovanni 1 Restall, Greg 1 Saks, Michael E. 1 Scheder, Dominik 1 Shen, Weina 1 Springsteel, Frederick Neil 1 Stern, Alan S. 1 Szegedy, Mario 1 Szemerédi, Endre 1 Takeuti, Gaisi 1 Talebanfard, Navid 1 Thérien, Denis 1 Turán, Gyorgy 1 Turzík, Daniel 1 Urban, Josef 1 Urquhart, Alasdair 1 Vavřín, Zdeněk 1 Visser, Albert 1 Vyskočil, Jiří
all top 5

### Serials

 8 Commentationes Mathematicae Universitatis Carolinae 7 Theoretical Computer Science 6 Algebra Universalis 6 The Journal of Symbolic Logic 6 Annals of Pure and Applied Logic 5 Information Processing Letters 5 Computational Complexity 4 Journal of Computer and System Sciences 4 Combinatorica 3 Archive for Mathematical Logic 2 Discrete Mathematics 2 Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 2 Information and Computation 2 Pokroky Matematiky, Fyziky & Astronomie 2 Theory of Computing Systems 2 Perspectives in Mathematical Logic 1 Acta Informatica 1 American Mathematical Monthly 1 Bulletin of the Australian Mathematical Society 1 Communications in Algebra 1 IEEE Transactions on Information Theory 1 Israel Journal of Mathematics 1 Fundamenta Mathematicae 1 Journal of Combinatorial Theory. Series B 1 Memoirs of the American Mathematical Society 1 Proceedings of the London Mathematical Society. Third Series 1 SIAM Journal on Computing 1 Transactions of the American Mathematical Society 1 Computers and Artificial Intelligence 1 Random Structures & Algorithms 1 Designs, Codes and Cryptography 1 Geometric and Functional Analysis. GAFA 1 Linear Algebra and its Applications 1 Zapiski Nauchnykh Seminarov POMI 1 Combinatorics, Probability and Computing 1 Mathematical Logic Quarterly (MLQ) 1 Finite Fields and their Applications 1 The Bulletin of Symbolic Logic 1 Chicago Journal of Theoretical Computer Science 1 Journal of the ACM 1 Bulletin of the European Association for Theoretical Computer Science EATCS 1 ACM Transactions on Computational Logic 1 Journal of Applied Logic 1 Lecture Notes in Logic 1 ACM Transactions on Computation Theory 1 Springer Monographs in Mathematics 1 Perspectives in Logic
all top 5

### Fields

 87 Computer science (68-XX) 78 Mathematical logic and foundations (03-XX) 23 Combinatorics (05-XX) 19 Information and communication theory, circuits (94-XX) 14 Order, lattices, ordered algebraic structures (06-XX) 7 Linear and multilinear algebra; matrix theory (15-XX) 7 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 5 History and biography (01-XX) 5 General algebraic systems (08-XX) 3 Probability theory and stochastic processes (60-XX) 2 General and overarching topics; collections (00-XX) 2 Operations research, mathematical programming (90-XX) 1 Number theory (11-XX) 1 Algebraic geometry (14-XX) 1 Group theory and generalizations (20-XX) 1 Functional analysis (46-XX) 1 Operator theory (47-XX) 1 Convex and discrete geometry (52-XX) 1 Statistics (62-XX) 1 Numerical analysis (65-XX) 1 Quantum theory (81-XX) 1 Biology and other natural sciences (92-XX)

### Citations contained in zbMATH Open

119 Publications have been cited 1,502 times in 1,057 Documents Cited by Year
Metamathematics of first-order arithmetic. Zbl 0781.03047
Hájek, Petr; Pudlák, Pavel
1993
Lower bounds for resolution and cutting plane proofs and monotone computations. Zbl 0945.03086
Pudlák, Pavel
1997
Metamathematics of first-order arithmetic. 2nd printing. Zbl 0889.03053
Hájek, Petr; Pudlák, Pavel
1998
Every finite lattice can be embedded in a finite partition lattice. Zbl 0433.06009
Pudlak, P.; Tuma, J.
1980
Propositional proof systems, the consistency of first order theories and the complexity of computations. Zbl 0696.03029
Krajíček, Jan; Pudlák, Pavel
1989
Cuts, consistency statements and interpretations. Zbl 0569.03024
Pudlák, Pavel
1985
An improved exponential-time algorithm for $$k$$-SAT. Zbl 1297.68217
Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis
2005
Threshold circuits of bounded depth. Zbl 0801.68052
Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György
1993
Bounded arithmetic and the polynomial hierarchy. Zbl 0736.03022
Krajíček, Jan; Pudlák, Pavel; Takeuti, Gaisi
1991
An exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Zbl 0843.03032
Krajíček, Jan; Pudlák, Pavel; Woods, Alan
1995
The lengths of proofs. Zbl 0920.03056
Pudlák, Pavel
1998
Congruence lattices of finite algebras and intervals in subgroup lattices of finite groups. Zbl 0386.06002
Pálfy, Péter Pál; Pudlák, Pavel
1980
The number of proof lines and the size of proofs in first order logic. Zbl 0644.03032
Krajíček, Jan; Pudlák, Pavel
1988
Lower bounds on Hilbert’s Nullstellensatz and propositional proofs. Zbl 0853.03017
Beame, Paul; Impagliazzo, Russell; Krajíček, Jan; Pitassi, Toniann; Pudlák, Pavel
1996
Some consequences of cryptographical conjectures for $$S_2^1$$ and EF. Zbl 0892.68029
Krajíček, Jan; Pudlák, Pavel
1998
Satisfiability coding lemma. Zbl 0940.68049
Paturi, Ramamohan; Pudlak, Pavel; Zane, Francis
1999
Quantified propositional calculi and fragments of bounded arithmetic. Zbl 0696.03031
Krajíček, Jan; Pudlák, Pavel
1990
Partition theorems for systems of finite subsets of integers. Zbl 0486.05006
Pudlák, Pavel; Rödl, Vojtěch
1982
A lower bound for DLL algorithms for $$k$$-SAT (Preliminary version). Zbl 0953.68150
Pudlák, Pavel; Impagliazzo, Russell
2000
Communication in bounded depth circuits. Zbl 0819.68090
Pudlák, P.
1994
On congruence lattices of lattices. Zbl 0562.06005
Pudlák, P.
1985
Lower bounds for the polynomial calculus and the Gröbner basis algorithm. Zbl 0946.68129
Impagliazzo, Russell; Pudlák, Pavel; Sgall, Jiří
1999
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Zbl 0890.03030
Buss, S.; Impagliazzo, R.; Krajíček, J.; Pudlák, P.; Razborov, A. A.; Sgall, J.
1997
MaLARea SG1 – machine learner for automated reasoning with semantic guidance. Zbl 1165.68434
Urban, Josef; Sutcliffe, Geoff; Pudlák, Petr; Vyskočil, Jiří
2008
Boolean circuits, tensor ranks, and communication complexity. Zbl 0870.68068
Pudlák, Pavel; Rödl, Vojtěch; Sgall, Jiří
1997
Some structural properties of low-rank matrices related to computational complexity. Zbl 0938.68059
Codenotti, B.; Pudlák, P.; Resta, G.
2000
On the computational power of depth-2 circuits with threshold and modulo gates. Zbl 0908.68110
Krause, Matthias; Pudlák, Pavel
1997
Computing Boolean functions by polynomials and threshold circuits. Zbl 0936.94022
Krause, Matthias; Pudlák, Pavel
1998
A lattice of chapters of mathematics (interpretations between theorems). Zbl 0696.03030
Mycielski, Jan; Pudlák, Pavel; Stern, Alan S.
1990
On the complexity of the propositional calculus. Zbl 0939.03065
Pudlák, Pavel
1999
A new proof of the congruence lattice representation theorem. Zbl 0358.08005
Pudlák, Pavel
1976
Proofs as games. Zbl 0983.03045
Pudlák, Pavel
2000
On reducibility and symmetry of disjoint NP pairs. Zbl 1045.68058
Pudlák, Pavel
2003
Some prime elements in the lattice of interpretability types. Zbl 0561.03014
Pudlák, Pavel
1983
Top-down lower bounds for depth-three circuits. Zbl 0838.68056
Håstad, Johan; Jukna, S.; Pudlák, P.
1995
Algebraic models of computation and interpolation for algebraic proof systems. Zbl 0901.03033
Pudlák, Pavel; Sgall, Jiří
1998
Pseudorandom sets and explicit constructions of Ramsey graphs. Zbl 1074.05088
Pudlák, Pavel; Rödl, Vojtěch
2004
Ramsey’s theorem in bounded arithmetic. Zbl 0795.03081
Pudlák, Pavel
1991
Monotone simulations of non-monotone proofs. Zbl 1034.03054
Atserias, Albert; Galesi, Nicola; Pudlák, Pavel
2002
Equilateral sets in $$l_p^n$$. Zbl 1034.46015
Alon, Noga; Pudlák, Pavel
2003
Some combinatorial-algebraic problems from complexity theory. Zbl 0824.68053
Pudlák, Pavel; Rödl, Vojtěch
1994
Pseudorandom generators for group products, extended abstract. Zbl 1288.68131
Koucký, Michal; Nimbhorkar, Prajakta; Pudlák, Pavel
2011
A lower bound on complexity of branching programs. Zbl 0572.68033
Pudlák, P.
1984
Graph complexity. Zbl 0681.68070
Pudlák, Pavel; Rödl, Vojtěch; Savický, Petr
1988
Superconcentrators of depths 2 and 3; odd levels help (rarely). Zbl 0802.68095
Alon, Noga; Pudlak, Pavel
1994
Logical foundations of mathematics and computational complexity. A gentle introduction. Zbl 1270.03001
Pudlák, Pavel
2013
On the computational power of depth 2 circuits with threshold and modulo gates. Zbl 1345.68130
Krause, Matthias; Pudlák, Pavel
1994
Cycles of nonzero elements in low rank matrices. Zbl 0996.05090
Pudlák, Pavel
2002
On the lengths of proofs of consistency. A survey of results. Zbl 0855.03032
Pudlák, Pavel
1996
Lower bounds to the complexity of symmetric Boolean functions. Zbl 0701.68044
Babai, L.; Pudlák, P.; Rödl, Vojtěch; Szemeredi, E.
1990
Constructive lower bounds for off-diagonal Ramsey numbers. Zbl 0988.05091
Alon, Noga; Pudlák, Pavel
2001
On the computational content of intuitionistic propositional proofs. Zbl 1009.03027
Buss, Samuel R.; Pudlák, Pavel
2001
On shifting networks. Zbl 0777.94025
Pudlák, Pavel; Savický, Petr
1993
How to lie without being (easily) convicted and the lengths of proofs in propositional calculus. Zbl 1044.03542
Pudlák, Pavel; Buss, Samuel R.
1995
Computation of rigidity of order $$n^ 2/r$$ for one simple matrix. Zbl 0753.15011
Pudlák, Pavel; Vavřín, Zdeněk
1991
The hierarchy of Boolean circuits. Zbl 0641.94028
Pudlák, Pavel
1987
A note on Boolean dimension of posets. Zbl 0683.06003
Nešetřil, Jaroslav; Pudlák, P.
1989
On the complexity of finding falsifying assignments for Herbrand disjunctions. Zbl 1378.03043
Pudlák, Pavel
2015
A note on monotone complexity and the rank of matrices. Zbl 1175.68189
Gál, Anna; Pudlák, Pavel
2003
Incompleteness in the finite domain. Zbl 1423.03245
Pudlák, Pavel
2017
On reducibility and symmetry of disjoint NP-pairs. Zbl 0999.68080
Pudlák, Pavel
2001
The observational predicate calculus and complexity of computations. Zbl 0311.02021
Pudlak, Pavel
1975
A note on bounded arithmetic. Zbl 0734.03030
Pudlák, P.
1990
A combinatorial approach to complexity. Zbl 0825.68483
Pudlák, Pavel; Rödl, Vojtěch
1992
Fragments of bounded arithmetic and the lengths of proofs. Zbl 1168.03044
Pudlák, Pavel
2008
Extensions of k-subsets to k+1-subsets - existence versus constructibility. Zbl 0495.68059
Poljak, S.; Turzik, D.; Pudlak, P.
1982
A definition of exponentiation by a bounded arithmetical formula. Zbl 0533.03032
Pudlák, Pavel
1983
Improved bounds to the length of proofs of finitistic consistency statements. Zbl 0635.03054
Pudlák, P.
1987
On a unification problem related to Kreisel’s conjecture. Zbl 0664.03037
Pudlák, Pavel
1988
Some constructive bounds on Ramsey numbers. Zbl 1200.05137
Kostochka, Alexandr; Pudlák, Pavel; Rödl, Vojtech
2010
Modified ranks of tensors and the size of circuits. Zbl 1310.68119
Pudlák, P.; Rödl, V.
1993
On the complexity of circuit satisfiability. Zbl 1293.68173
Paturi, Ramamohan; Pudlak, Pavel
2010
The space complexity of cutting planes refutations. Zbl 1388.03055
Galesi, Nicola; Pudlák, Pavel; Thapen, Neil
2015
Twelve problems in proof complexity. Zbl 1142.03369
Pudlák, Pavel
2008
Alternating minima and maxima, Nash equilibria and bounded arithmetic. Zbl 1345.03108
Pudlák, Pavel; Thapen, Neil
2012
Distributivity of strongly representable lattices. Zbl 0358.06024
Pudlák, Pavel
1977
On the length of proofs of finitistic consistency statements in first order theories. Zbl 0619.03037
Pudlák, Pavel
1986
On convex complexity measures. Zbl 1192.68295
Hrubeš, P.; Jukna, S.; Kulikov, A.; Pudlák, P.
2010
Complexity theory and genetics: The computational power of crossing over. Zbl 1005.68066
Pudlák, P.
2001
Yeast graphs and fermentation of algebraic lattices. Zbl 0358.06013
Pudlák, P.; Tůma, J.
1976
Every finite lattice can be embedded in the lattice of all equivalences over a finite set. Zbl 0363.06006
Pudlak, Pavel; Tuma, Jiri
1977
Complexity in mechanized hypothesis formation. Zbl 0404.68097
Pudlak, Pavel; Springsteel, Frederick N.
1979
Propositional provability and models of weak arithmetic. Zbl 0925.03211
Krajíček, Jan; Pudlák, Pavel
1990
An application of Hindman’s theorem to a problem on communication complexity. Zbl 1088.68612
Pudlák, Pavel
2003
Bounds for Hodes-Specker theorem. Zbl 0551.03022
Pudlák, Pavel
1984
Kreisel’s conjecture for $$L\exists_ 1$$. (Including a postscript by Georg Kreisel). Zbl 0812.03024
Baaz, Matthias; Pudlák, Pavel
1993
A note on the use of determinant for proving lower bounds on the size of linear circuits. Zbl 1338.68117
Pudlák, Pavel
2000
Parity games and propositional proofs. Zbl 1291.03111
Beckmann, Arnold; Pudlák, Pavel; Thapen, Neil
2014
Satisfiability – algorithms and logic (extended abstract). Zbl 0911.03018
Pudlák, Pavel
1998
A lower bound on the size of resolution proofs of the Ramsey theorem. Zbl 1243.68187
Pudlák, Pavel
2012
Circuit lower bounds and linear codes. Zbl 1079.94018
Paturi, R.; Pudlák, P.
2004
Consistency and games – in search of new combinatorial principles. Zbl 1105.03059
Pudlák, Pavel
2006
On equational theories of semilattices with operators. Zbl 0708.08003
Ježek, J.; Pudlák, P.; Tuma, J.
1990
Some relations between subsystems of arithmetic and complexity of computations. Zbl 0752.03029
Pudlák, Pavel
1992
Abbreviating proofs using metamathematical rules. Zbl 0794.03080
Hájek, Petr; Montagna, Franco; Pudlák, Pavel
1993
Bounded-depth circuits: separating wires from gates (extended abstract). Zbl 1192.68298
Koucký, Michal; Pudlák, Pavel; Thérien, Denis
2005
On extracting computations from propositional proofs (a survey). Zbl 1245.68089
Pudlák, Pavel
2010
Decorated linear order types and the theory of concatenation. Zbl 1244.03162
Čačić, Vedran; Pudlák, Pavel; Restall, Greg; Urquhart, Alasdair; Visser, Albert
2010
Classification of 8-dimensional trilinear alternating forms over $$\mathrm{GF}(2)$$. Zbl 1322.15012
Hora, Jan; Pudlák, Petr
2015
Linear tree codes and the problem of explicit constructions. Zbl 1366.94749
Pudlák, Pavel
2016
Classification of 9-dimensional trilinear alternating forms over $$\mathrm{GF}(2)$$. Zbl 1461.15016
Hora, Jan; Pudlák, Petr
2021
A note on monotone real circuits. Zbl 1422.68115
Hrubeš, Pavel; Pudlák, Pavel
2018
Incompleteness in the finite domain. Zbl 1423.03245
Pudlák, Pavel
2017
The complexity of proving that a graph is Ramsey. Zbl 1399.03021
Lauria, Massimo; Pudlák, Pavel; Rödl, Vojtěch; Thapen, Neil
2017
Representations of monotone Boolean functions by linear programs. Zbl 1440.68078
de Oliveira Oliveira, Mateus; Pudlák, Pavel
2017
Tighter hard instances for PPSZ. Zbl 1441.68238
Pudlák, Pavel; Scheder, Dominik; Talebanfard, Navid
2017
Linear tree codes and the problem of explicit constructions. Zbl 1366.94749
Pudlák, Pavel
2016
Metamathematics of first-order arithmetic. Reprint of the 1993 original published by Springer. Zbl 1365.03008
Hájek, Petr; Pudlák, Pavel
2016
On the complexity of finding falsifying assignments for Herbrand disjunctions. Zbl 1378.03043
Pudlák, Pavel
2015
The space complexity of cutting planes refutations. Zbl 1388.03055
Galesi, Nicola; Pudlák, Pavel; Thapen, Neil
2015
Classification of 8-dimensional trilinear alternating forms over $$\mathrm{GF}(2)$$. Zbl 1322.15012
Hora, Jan; Pudlák, Petr
2015
Parity games and propositional proofs. Zbl 1291.03111
Beckmann, Arnold; Pudlák, Pavel; Thapen, Neil
2014
Logical foundations of mathematics and computational complexity. A gentle introduction. Zbl 1270.03001
Pudlák, Pavel
2013
The complexity of proving that a graph is Ramsey. Zbl 1336.03066
Lauria, Massimo; Pudlák, Pavel; Rödl, Vojtěch; Thapen, Neil
2013
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. Zbl 1364.94780
Gál, Anna; Hansen, Kristoffer Arnsfelt; Koucký, Michal; Pudlák, Pavel; Viola, Emanuele
2013
Alternating minima and maxima, Nash equilibria and bounded arithmetic. Zbl 1345.03108
Pudlák, Pavel; Thapen, Neil
2012
A lower bound on the size of resolution proofs of the Ramsey theorem. Zbl 1243.68187
Pudlák, Pavel
2012
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. Zbl 1286.94108
Gál, Anna; Hansen, Kristoffer Arnsfelt; Koucký, Michal; Pudlák, Pavel; Viola, Emanuele
2012
Pseudorandom generators for group products, extended abstract. Zbl 1288.68131
Koucký, Michal; Nimbhorkar, Prajakta; Pudlák, Pavel
2011
Some constructive bounds on Ramsey numbers. Zbl 1200.05137
Kostochka, Alexandr; Pudlák, Pavel; Rödl, Vojtech
2010
On the complexity of circuit satisfiability. Zbl 1293.68173
Paturi, Ramamohan; Pudlak, Pavel
2010
On convex complexity measures. Zbl 1192.68295
Hrubeš, P.; Jukna, S.; Kulikov, A.; Pudlák, P.
2010
On extracting computations from propositional proofs (a survey). Zbl 1245.68089
Pudlák, Pavel
2010
Decorated linear order types and the theory of concatenation. Zbl 1244.03162
Čačić, Vedran; Pudlák, Pavel; Restall, Greg; Urquhart, Alasdair; Visser, Albert
2010
Solving the \$100 modal logic challenge. Zbl 1161.03302
Rabe, Florian; Pudlák, Petr; Sutcliffe, Geoff; Shen, Weina
2009
MaLARea SG1 – machine learner for automated reasoning with semantic guidance. Zbl 1165.68434
Urban, Josef; Sutcliffe, Geoff; Pudlák, Petr; Vyskočil, Jiří
2008
Fragments of bounded arithmetic and the lengths of proofs. Zbl 1168.03044
Pudlák, Pavel
2008
Twelve problems in proof complexity. Zbl 1142.03369
Pudlák, Pavel
2008
Consistency and games – in search of new combinatorial principles. Zbl 1105.03059
Pudlák, Pavel
2006
On explicit Ramsey graphs and estimates of the number of sums and products. Zbl 1110.05069
Pudlák, Pavel
2006
An improved exponential-time algorithm for $$k$$-SAT. Zbl 1297.68217
Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis
2005
Bounded-depth circuits: separating wires from gates (extended abstract). Zbl 1192.68298
Koucký, Michal; Pudlák, Pavel; Thérien, Denis
2005
Pseudorandom sets and explicit constructions of Ramsey graphs. Zbl 1074.05088
Pudlák, Pavel; Rödl, Vojtěch
2004
Circuit lower bounds and linear codes. Zbl 1079.94018
Paturi, R.; Pudlák, P.
2004
On reducibility and symmetry of disjoint NP pairs. Zbl 1045.68058
Pudlák, Pavel
2003
Equilateral sets in $$l_p^n$$. Zbl 1034.46015
Alon, Noga; Pudlák, Pavel
2003
A note on monotone complexity and the rank of matrices. Zbl 1175.68189
Gál, Anna; Pudlák, Pavel
2003
An application of Hindman’s theorem to a problem on communication complexity. Zbl 1088.68612
Pudlák, Pavel
2003
Monotone simulations of non-monotone proofs. Zbl 1034.03054
Atserias, Albert; Galesi, Nicola; Pudlák, Pavel
2002
Cycles of nonzero elements in low rank matrices. Zbl 0996.05090
Pudlák, Pavel
2002
Constructive lower bounds for off-diagonal Ramsey numbers. Zbl 0988.05091
Alon, Noga; Pudlák, Pavel
2001
On the computational content of intuitionistic propositional proofs. Zbl 1009.03027
Buss, Samuel R.; Pudlák, Pavel
2001
On reducibility and symmetry of disjoint NP-pairs. Zbl 0999.68080
Pudlák, Pavel
2001
Complexity theory and genetics: The computational power of crossing over. Zbl 1005.68066
Pudlák, P.
2001
A lower bound for DLL algorithms for $$k$$-SAT (Preliminary version). Zbl 0953.68150
Pudlák, Pavel; Impagliazzo, Russell
2000
Some structural properties of low-rank matrices related to computational complexity. Zbl 0938.68059
Codenotti, B.; Pudlák, P.; Resta, G.
2000
Proofs as games. Zbl 0983.03045
Pudlák, Pavel
2000
A note on the use of determinant for proving lower bounds on the size of linear circuits. Zbl 1338.68117
Pudlák, Pavel
2000
Satisfiability coding lemma. Zbl 0940.68049
Paturi, Ramamohan; Pudlak, Pavel; Zane, Francis
1999
Lower bounds for the polynomial calculus and the Gröbner basis algorithm. Zbl 0946.68129
Impagliazzo, Russell; Pudlák, Pavel; Sgall, Jiří
1999
On the complexity of the propositional calculus. Zbl 0939.03065
Pudlák, Pavel
1999
Metamathematics of first-order arithmetic. 2nd printing. Zbl 0889.03053
Hájek, Petr; Pudlák, Pavel
1998
The lengths of proofs. Zbl 0920.03056
Pudlák, Pavel
1998
Some consequences of cryptographical conjectures for $$S_2^1$$ and EF. Zbl 0892.68029
Krajíček, Jan; Pudlák, Pavel
1998
Computing Boolean functions by polynomials and threshold circuits. Zbl 0936.94022
Krause, Matthias; Pudlák, Pavel
1998
Algebraic models of computation and interpolation for algebraic proof systems. Zbl 0901.03033
Pudlák, Pavel; Sgall, Jiří
1998
Satisfiability – algorithms and logic (extended abstract). Zbl 0911.03018
Pudlák, Pavel
1998
Lower bounds for resolution and cutting plane proofs and monotone computations. Zbl 0945.03086
Pudlák, Pavel
1997
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Zbl 0890.03030
Buss, S.; Impagliazzo, R.; Krajíček, J.; Pudlák, P.; Razborov, A. A.; Sgall, J.
1997
Boolean circuits, tensor ranks, and communication complexity. Zbl 0870.68068
Pudlák, Pavel; Rödl, Vojtěch; Sgall, Jiří
1997
On the computational power of depth-2 circuits with threshold and modulo gates. Zbl 0908.68110
Krause, Matthias; Pudlák, Pavel
1997
An upper bound for a communication game related to time-space tradeoffs. Zbl 0868.68086
Pudlák, Pavel; Sgall, Jiří
1997
On sparse parity check matrices. Zbl 0902.94018
Lefmann, Hanno; Pudlák, Pavel; Savický, Petr
1997
Lower bounds on Hilbert’s Nullstellensatz and propositional proofs. Zbl 0853.03017
Beame, Paul; Impagliazzo, Russell; Krajíček, Jan; Pitassi, Toniann; Pudlák, Pavel
1996
On the lengths of proofs of consistency. A survey of results. Zbl 0855.03032
Pudlák, Pavel
1996
A bottom-up approach to foundations of mathematics. Zbl 0857.03023
Pudlák, Pavel
1996
An exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Zbl 0843.03032
Krajíček, Jan; Pudlák, Pavel; Woods, Alan
1995
Top-down lower bounds for depth-three circuits. Zbl 0838.68056
Håstad, Johan; Jukna, S.; Pudlák, P.
1995
How to lie without being (easily) convicted and the lengths of proofs in propositional calculus. Zbl 1044.03542
Pudlák, Pavel; Buss, Samuel R.
1995
Communication in bounded depth circuits. Zbl 0819.68090
Pudlák, P.
1994
Some combinatorial-algebraic problems from complexity theory. Zbl 0824.68053
Pudlák, Pavel; Rödl, Vojtěch
1994
Superconcentrators of depths 2 and 3; odd levels help (rarely). Zbl 0802.68095
Alon, Noga; Pudlak, Pavel
1994
On the computational power of depth 2 circuits with threshold and modulo gates. Zbl 1345.68130
Krause, Matthias; Pudlák, Pavel
1994
Metamathematics of first-order arithmetic. Zbl 0781.03047
Hájek, Petr; Pudlák, Pavel
1993
Threshold circuits of bounded depth. Zbl 0801.68052
Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György
1993
On shifting networks. Zbl 0777.94025
Pudlák, Pavel; Savický, Petr
1993
Modified ranks of tensors and the size of circuits. Zbl 1310.68119
Pudlák, P.; Rödl, V.
1993
Kreisel’s conjecture for $$L\exists_ 1$$. (Including a postscript by Georg Kreisel). Zbl 0812.03024
Baaz, Matthias; Pudlák, Pavel
1993
Abbreviating proofs using metamathematical rules. Zbl 0794.03080
Hájek, Petr; Montagna, Franco; Pudlák, Pavel
1993
A combinatorial approach to complexity. Zbl 0825.68483
Pudlák, Pavel; Rödl, Vojtěch
1992
Some relations between subsystems of arithmetic and complexity of computations. Zbl 0752.03029
Pudlák, Pavel
1992
Bounded arithmetic and the polynomial hierarchy. Zbl 0736.03022
Krajíček, Jan; Pudlák, Pavel; Takeuti, Gaisi
1991
Ramsey’s theorem in bounded arithmetic. Zbl 0795.03081
Pudlák, Pavel
1991
Computation of rigidity of order $$n^ 2/r$$ for one simple matrix. Zbl 0753.15011
Pudlák, Pavel; Vavřín, Zdeněk
1991
Quantified propositional calculi and fragments of bounded arithmetic. Zbl 0696.03031
Krajíček, Jan; Pudlák, Pavel
1990
A lattice of chapters of mathematics (interpretations between theorems). Zbl 0696.03030
Mycielski, Jan; Pudlák, Pavel; Stern, Alan S.
1990
Lower bounds to the complexity of symmetric Boolean functions. Zbl 0701.68044
Babai, L.; Pudlák, P.; Rödl, Vojtěch; Szemeredi, E.
1990
A note on bounded arithmetic. Zbl 0734.03030
Pudlák, P.
1990
Propositional provability and models of weak arithmetic. Zbl 0925.03211
Krajíček, Jan; Pudlák, Pavel
1990
On equational theories of semilattices with operators. Zbl 0708.08003
Ježek, J.; Pudlák, P.; Tuma, J.
1990
Propositional proof systems, the consistency of first order theories and the complexity of computations. Zbl 0696.03029
Krajíček, Jan; Pudlák, Pavel
1989
A note on Boolean dimension of posets. Zbl 0683.06003
Nešetřil, Jaroslav; Pudlák, P.
1989
On the structure of initial segments of models of arithmetic. Zbl 0678.03026
Krajíček, Jan; Pudlák, Pavel
1989
The number of proof lines and the size of proofs in first order logic. Zbl 0644.03032
Krajíček, Jan; Pudlák, Pavel
1988
Graph complexity. Zbl 0681.68070
Pudlák, Pavel; Rödl, Vojtěch; Savický, Petr
1988
On a unification problem related to Kreisel’s conjecture. Zbl 0664.03037
Pudlák, Pavel
1988
The hierarchy of Boolean circuits. Zbl 0641.94028
Pudlák, Pavel
1987
Improved bounds to the length of proofs of finitistic consistency statements. Zbl 0635.03054
Pudlák, P.
1987
On the length of proofs of finitistic consistency statements in first order theories. Zbl 0619.03037
Pudlák, Pavel
1986
Cuts, consistency statements and interpretations. Zbl 0569.03024
Pudlák, Pavel
1985
...and 19 more Documents
all top 5

### Cited by 1,078 Authors

 30 Pudlák, Pavel 26 Krajíček, Jan 24 Visser, Albert 23 Beyersdorff, Olaf 18 Jeřábek, Emil 16 Buss, Samuel R. 15 Kołodziejczyk, Leszek Aleksander 14 Urban, Josef 13 Thapen, Neil 11 Alon, Noga M. 11 Buss, Sam 11 Hirsch, Edward A. 11 Sherstov, Alexander A. 10 Impagliazzo, Russell 10 Lauria, Massimo 10 Pitassi, Toniann 9 Atserias, Albert 9 Beckmann, Arnold 9 Yukna, Stasys P. 8 Baaz, Matthias 8 Galesi, Nicola 8 Kurahashi, Taishi 8 Nicolai, Carlo 8 Servedio, Rocco A. 8 Willard, Dan E. 8 Yokoyama, Keita 7 Aschbacher, Michael George 7 Cordón-Franco, Andrés 7 Ferreira, Fernando 7 Hetzl, Stefan 7 Kaliszyk, Cezary 7 Lara-Martín, Francisco Felix 7 Müller, Moritz 7 Razborov, Aleksandr Aleksandrovich 7 Todorcevic, Stevo B. 7 Wehrung, Friedrich 6 Beklemishev, Lev D. 6 Cook, Stephen Arthur 6 Enayat, Ali 6 Fernández Margarit, Alejandro 6 Göös, Mika 6 Joosten, Joost J. 6 Pakhomov, Fedor N. 6 Pollett, Chris 6 Rodl, Vojtech 6 Seto, Kazuhisa 6 Shore, Richard Arnold 6 Tůma, Jiří 6 Tzameret, Iddo 6 Urquhart, Alasdair 5 Adamowicz, Zofia 5 Avigad, Jeremy 5 Beimel, Amos 5 Bonet, Maria Luisa 5 Dean, Walter 5 Dobrinen, Natasha L. 5 Hájek, Petr 5 Hansen, Kristoffer Arnsfelt 5 Hrubeš, Pavel 5 Kabanets, Valentine 5 Kolokolova, Antonina 5 Maciel, Alexis 5 Nordström, Jakob 5 Papadimitriou, Christos Harilaos 5 Paturi, Ramamohan 5 Podol’skiĭ, Vladimir Vladimirovich 5 Shafer, Paul 5 Slaman, Theodore A. 5 Talebanfard, Navid 5 Tamaki, Suguru 5 Thérien, Denis 5 Walsh, Sean 5 Wegener, Ingo 5 Williams, Richard Ryan 5 Zdanowski, Konrad 4 Chattopadhyay, Arkadev 4 Codenotti, Bruno 4 Esteban, Juan Luis 4 Glaßer, Christian 4 Grigor’ev, Dmitriĭ Yur’evich 4 Itsykson, Dmitry M. 4 Kjos-Hanssen, Bjørn 4 Köbler, Johannes 4 Koucký, Michal 4 Kühlwein, Daniel 4 Lampe, William A. 4 McMillan, Kenneth L. 4 O’Donnell, Ryan 4 Pich, Ján 4 Sadowski, Zenon 4 Salehi, Saeed 4 Sarma M. N., Jayalal 4 Selman, Alan L. 4 Shavrukov, V. Yu. 4 Šíma, Jiří 4 Straßburger, Lutz 4 Swanepoel, Konrad J. 4 Takeuti, Gaisi 4 Torán, Jacobo 4 Turán, Gyorgy ...and 978 more Authors
all top 5

### Cited in 151 Serials

 102 Annals of Pure and Applied Logic 74 The Journal of Symbolic Logic 66 Theoretical Computer Science 48 Archive for Mathematical Logic 38 Journal of Computer and System Sciences 36 Mathematical Logic Quarterly (MLQ) 31 Computational Complexity 30 Information Processing Letters 27 Algebra Universalis 26 Information and Computation 22 SIAM Journal on Computing 22 The Bulletin of Symbolic Logic 22 The Review of Symbolic Logic 16 Journal of Automated Reasoning 14 Notre Dame Journal of Formal Logic 14 Theory of Computing Systems 13 Discrete Applied Mathematics 13 Transactions of the American Mathematical Society 12 Discrete Mathematics 12 Journal of Algebra 9 Advances in Mathematics 9 Proceedings of the American Mathematical Society 9 Combinatorica 9 Order 9 Logical Methods in Computer Science 7 Journal of Combinatorial Theory. Series A 7 International Journal of Algebra and Computation 7 Journal of Mathematical Sciences (New York) 7 Annals of Mathematics and Artificial Intelligence 6 Artificial Intelligence 6 Studia Logica 6 Journal of Symbolic Computation 6 Algorithmica 6 Linear Algebra and its Applications 6 The Electronic Journal of Combinatorics 6 Journal of Mathematical Logic 5 European Journal of Combinatorics 5 SIAM Journal on Discrete Mathematics 5 Formal Methods in System Design 5 ACM Transactions on Computational Logic 4 Czechoslovak Mathematical Journal 4 Journal of Pure and Applied Algebra 3 Communications in Algebra 3 Israel Journal of Mathematics 3 Mathematical Notes 3 Fundamenta Mathematicae 3 Journal of Philosophical Logic 3 Semigroup Forum 3 MSCS. Mathematical Structures in Computer Science 3 International Journal of Foundations of Computer Science 3 Combinatorics, Probability and Computing 3 Annals of Mathematics. Second Series 3 Proceedings of the Steklov Institute of Mathematics 3 Mathematics in Computer Science 3 Theory of Computing 2 Russian Mathematical Surveys 2 Algebra and Logic 2 Archiv der Mathematik 2 Commentationes Mathematicae Universitatis Carolinae 2 Journal of Combinatorial Theory. Series B 2 Journal of Functional Analysis 2 Journal of Graph Theory 2 Mathematika 2 Synthese 2 Topology and its Applications 2 Operations Research Letters 2 History and Philosophy of Logic 2 Graphs and Combinatorics 2 Journal of the American Mathematical Society 2 Journal of Cryptology 2 Forum Mathematicum 2 Random Structures & Algorithms 2 Neural Computation 2 Discrete Mathematics and Applications 2 Selecta Mathematica. New Series 2 Soft Computing 2 Journal of Combinatorial Optimization 2 Journal of the ACM 2 Interdisciplinary Information Sciences (IIS) 2 Erkenntnis 2 Journal of the Australian Mathematical Society 2 Journal of Applied Logic 2 Logica Universalis 2 Forum of Mathematics, Sigma 1 Archiv für Mathematische Logik und Grundlagenforschung 1 Bulletin of the Australian Mathematical Society 1 Lithuanian Mathematical Journal 1 Moscow University Mathematics Bulletin 1 Nuclear Physics. B 1 Periodica Mathematica Hungarica 1 Physica A 1 Rocky Mountain Journal of Mathematics 1 Studia Mathematica 1 The Mathematical Intelligencer 1 Theory of Probability and its Applications 1 Applied Mathematics and Computation 1 Colloquium Mathematicum 1 Demonstratio Mathematica 1 Fuzzy Sets and Systems 1 Information Sciences ...and 51 more Serials
all top 5

### Cited in 35 Fields

 570 Mathematical logic and foundations (03-XX) 477 Computer science (68-XX) 134 Combinatorics (05-XX) 110 Order, lattices, ordered algebraic structures (06-XX) 74 Information and communication theory, circuits (94-XX) 46 General algebraic systems (08-XX) 39 Group theory and generalizations (20-XX) 27 Operations research, mathematical programming (90-XX) 20 Linear and multilinear algebra; matrix theory (15-XX) 18 Number theory (11-XX) 13 Functional analysis (46-XX) 13 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 12 Convex and discrete geometry (52-XX) 11 History and biography (01-XX) 11 Probability theory and stochastic processes (60-XX) 9 General topology (54-XX) 8 General and overarching topics; collections (00-XX) 8 Commutative algebra (13-XX) 7 Geometry (51-XX) 6 Field theory and polynomials (12-XX) 5 Quantum theory (81-XX) 4 Algebraic geometry (14-XX) 4 Associative rings and algebras (16-XX) 4 Category theory; homological algebra (18-XX) 4 Numerical analysis (65-XX) 3 Statistics (62-XX) 3 Biology and other natural sciences (92-XX) 2 Real functions (26-XX) 2 Operator theory (47-XX) 1 $$K$$-theory (19-XX) 1 Topological groups, Lie groups (22-XX) 1 Measure and integration (28-XX) 1 Difference and functional equations (39-XX) 1 Algebraic topology (55-XX) 1 Global analysis, analysis on manifolds (58-XX)