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