Edit Profile (opens in new tab) Pudlák, Pavel Co-Author Distance Author ID: pudlak.pavel Published as: Pudlák, Pavel; Pudlák, P.; Pudlak, Pavel; Pudlák, Petr; Pudlak, P. more...less Homepage: http://users.math.cas.cz/~pudlak/ Documents Indexed: 155 Publications since 1975, including 7 Books 2 Contributions as Editor Co-Authors: 79 Co-Authors with 97 Joint Publications 2,792 Co-Co-Authors all top 5 Co-Authors 60 single-authored 12 Rodl, Vojtech 11 Krajíček, Jan 8 Thapen, Neil 6 Hájek, Petr 6 Sgall, Jiří 5 Paturi, Ramamohan 5 Tůma, Jiří 4 Buss, Samuel R. 4 Gavinsky, Dmitry 4 Impagliazzo, Russell 4 Koucký, Michal 4 Krause, Matthias 3 Alon, Noga 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ří 1 Woods, Alan Robert 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 Combinatorica 5 Computational Complexity 4 Journal of Computer and System Sciences 3 Pokroky Matematiky, Fyziky & Astronomie 3 Archive for Mathematical Logic 2 Discrete Mathematics 2 Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 2 Information and Computation 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 89 Computer science (68-XX) 78 Mathematical logic and foundations (03-XX) 24 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) 6 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 130 Publications have been cited 1,787 times in 1,239 Documents Cited by ▼ Year ▼ Metamathematics of first-order arithmetic. Zbl 0781.03047Hájek, Petr; Pudlák, Pavel 213 1993 Lower bounds for resolution and cutting plane proofs and monotone computations. Zbl 0945.03086Pudlák, Pavel 92 1997 Metamathematics of first-order arithmetic. 2nd printing. Zbl 0889.03053Hájek, Petr; Pudlák, Pavel 66 1998 Threshold circuits of bounded depth. Zbl 0801.68052Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György 61 1993 An improved exponential-time algorithm for \(k\)-SAT. Zbl 1297.68217Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis 59 2005 Every finite lattice can be embedded in a finite partition lattice. Zbl 0433.06009Pudlak, P.; Tuma, J. 56 1980 Propositional proof systems, the consistency of first order theories and the complexity of computations. Zbl 0696.03029Krajíček, Jan; Pudlák, Pavel 56 1989 Cuts, consistency statements and interpretations. Zbl 0569.03024Pudlák, Pavel 53 1985 Bounded arithmetic and the polynomial hierarchy. Zbl 0736.03022Krajíček, Jan; Pudlák, Pavel; Takeuti, Gaisi 44 1991 The lengths of proofs. Zbl 0920.03056Pudlák, Pavel 43 1998 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 42 1995 Congruence lattices of finite algebras and intervals in subgroup lattices of finite groups. Zbl 0386.06002Pálfy, Péter Pál; Pudlák, Pavel 39 1980 Lower bounds on Hilbert’s Nullstellensatz and propositional proofs. Zbl 0853.03017Beame, Paul; Impagliazzo, Russell; Krajíček, Jan; Pitassi, Toniann; Pudlák, Pavel 33 1996 Satisfiability coding lemma. Zbl 0940.68049Paturi, Ramamohan; Pudlak, Pavel; Zane, Francis 32 1999 Some consequences of cryptographical conjectures for \(S_2^1\) and EF. Zbl 0892.68029Krajíček, Jan; Pudlák, Pavel 31 1998 The number of proof lines and the size of proofs in first order logic. Zbl 0644.03032Krajíček, Jan; Pudlák, Pavel 31 1988 MaLARea SG1 – machine learner for automated reasoning with semantic guidance. Zbl 1165.68434Urban, Josef; Sutcliffe, Geoff; Pudlák, Petr; Vyskočil, Jiří 28 2008 Quantified propositional calculi and fragments of bounded arithmetic. Zbl 0696.03031Krajíček, Jan; Pudlák, Pavel 28 1990 Lower bounds for the polynomial calculus and the Gröbner basis algorithm. Zbl 0946.68129Impagliazzo, Russell; Pudlák, Pavel; Sgall, Jiří 27 1999 Partition theorems for systems of finite subsets of integers. Zbl 0486.05006Pudlák, Pavel; Rödl, Vojtěch 26 1982 A lower bound for DLL algorithms for \(k\)-SAT (Preliminary version). Zbl 0953.68150Pudlák, Pavel; Impagliazzo, Russell 26 2000 Communication in bounded depth circuits. Zbl 0819.68090Pudlák, P. 25 1994 Boolean circuits, tensor ranks, and communication complexity. Zbl 0870.68068Pudlák, Pavel; Rödl, Vojtěch; Sgall, Jiří 23 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. 21 1997 On congruence lattices of lattices. Zbl 0562.06005Pudlák, P. 21 1985 On the computational power of depth-2 circuits with threshold and modulo gates. Zbl 0908.68110Krause, Matthias; Pudlák, Pavel 20 1997 Some structural properties of low-rank matrices related to computational complexity. Zbl 0938.68059Codenotti, B.; Pudlák, P.; Resta, G. 20 2000 Proofs as games. Zbl 0983.03045Pudlák, Pavel 19 2000 On the complexity of the propositional calculus. Zbl 0939.03065Pudlák, Pavel 19 1999 On reducibility and symmetry of disjoint NP pairs. Zbl 1045.68058Pudlák, Pavel 18 2003 Computing Boolean functions by polynomials and threshold circuits. Zbl 0936.94022Krause, Matthias; Pudlák, Pavel 18 1998 A lattice of chapters of mathematics (interpretations between theorems). Zbl 0696.03030Mycielski, Jan; Pudlák, Pavel; Stern, Alan S. 18 1990 A new proof of the congruence lattice representation theorem. Zbl 0358.08005Pudlák, Pavel 15 1976 Some prime elements in the lattice of interpretability types. Zbl 0561.03014Pudlák, Pavel 15 1983 Equilateral sets in \(l_p^n\). Zbl 1034.46015Alon, Noga; Pudlák, Pavel 14 2003 Top-down lower bounds for depth-three circuits. Zbl 0838.68056Håstad, Johan; Jukna, S.; Pudlák, P. 14 1995 Algebraic models of computation and interpolation for algebraic proof systems. Zbl 0901.03033Pudlák, Pavel; Sgall, Jiří 13 1998 Pseudorandom generators for group products, extended abstract. Zbl 1288.68131Koucký, Michal; Nimbhorkar, Prajakta; Pudlák, Pavel 13 2011 Graph complexity. Zbl 0681.68070Pudlák, Pavel; Rödl, Vojtěch; Savický, Petr 12 1988 Pseudorandom sets and explicit constructions of Ramsey graphs. Zbl 1074.05088Pudlák, Pavel; Rödl, Vojtěch 11 2004 Ramsey’s theorem in bounded arithmetic. Zbl 0795.03081Pudlák, Pavel 11 1991 Superconcentrators of depths 2 and 3; odd levels help (rarely). Zbl 0802.68095Alon, Noga; Pudlak, Pavel 11 1994 On the computational power of depth 2 circuits with threshold and modulo gates. Zbl 1345.68130Krause, Matthias; Pudlák, Pavel 10 1994 Monotone simulations of non-monotone proofs. Zbl 1034.03054Atserias, Albert; Galesi, Nicola; Pudlák, Pavel 10 2002 How to lie without being (easily) convicted and the lengths of proofs in propositional calculus. Zbl 1044.03542Pudlák, Pavel; Buss, Samuel R. 10 1995 Logical foundations of mathematics and computational complexity. A gentle introduction. Zbl 1270.03001Pudlák, Pavel 10 2013 A lower bound on complexity of branching programs. Zbl 0572.68033Pudlák, P. 10 1984 Some combinatorial-algebraic problems from complexity theory. Zbl 0824.68053Pudlák, Pavel; Rödl, Vojtěch 10 1994 On the lengths of proofs of consistency. A survey of results. Zbl 0855.03032Pudlák, Pavel 9 1996 Constructive lower bounds for off-diagonal Ramsey numbers. Zbl 0988.05091Alon, Noga; Pudlák, Pavel 9 2001 Incompleteness in the finite domain. Zbl 1423.03245Pudlák, Pavel 9 2017 On shifting networks. Zbl 0777.94025Pudlák, Pavel; Savický, Petr 8 1993 On the computational content of intuitionistic propositional proofs. Zbl 1009.03027Buss, Samuel R.; Pudlák, Pavel 8 2001 Cycles of nonzero elements in low rank matrices. Zbl 0996.05090Pudlák, Pavel 8 2002 Lower bounds to the complexity of symmetric Boolean functions. Zbl 0701.68044Babai, L.; Pudlák, P.; Rödl, Vojtěch; Szemeredi, E. 8 1990 On the complexity of circuit satisfiability. Zbl 1293.68173Paturi, Ramamohan; Pudlak, Pavel 7 2010 Improved bounds to the length of proofs of finitistic consistency statements. Zbl 0635.03054Pudlák, P. 7 1987 On the complexity of finding falsifying assignments for Herbrand disjunctions. Zbl 1378.03043Pudlák, Pavel 7 2015 A note on Boolean dimension of posets. Zbl 0683.06003Nešetřil, Jaroslav; Pudlák, P. 7 1989 Computation of rigidity of order \(n^ 2/r\) for one simple matrix. Zbl 0753.15011Pudlák, Pavel; Vavřín, Zdeněk 6 1991 On reducibility and symmetry of disjoint NP-pairs. Zbl 0999.68080Pudlák, Pavel 6 2001 Some constructive bounds on Ramsey numbers. Zbl 1200.05137Kostochka, Alexandr; Pudlák, Pavel; Rödl, Vojtech 6 2010 A note on monotone complexity and the rank of matrices. Zbl 1175.68189Gál, Anna; Pudlák, Pavel 6 2003 The hierarchy of Boolean circuits. Zbl 0641.94028Pudlák, Pavel 6 1987 Modified ranks of tensors and the size of circuits. Zbl 1310.68119Pudlák, P.; Rödl, V. 6 1993 Extensions of k-subsets to k+1-subsets - existence versus constructibility. Zbl 0495.68059Poljak, S.; Turzik, D.; Pudlak, P. 5 1982 A note on the use of determinant for proving lower bounds on the size of linear circuits. Zbl 1338.68117Pudlák, Pavel 5 2000 A combinatorial approach to complexity. Zbl 0825.68483Pudlák, Pavel; Rödl, Vojtěch 5 1992 A note on bounded arithmetic. Zbl 0734.03030Pudlák, P. 5 1990 The observational predicate calculus and complexity of computations. Zbl 0311.02021Pudlak, Pavel 5 1975 Alternating minima and maxima, Nash equilibria and bounded arithmetic. Zbl 1345.03108Pudlák, Pavel; Thapen, Neil 5 2012 A definition of exponentiation by a bounded arithmetical formula. Zbl 0533.03032Pudlák, Pavel 5 1983 On a unification problem related to Kreisel’s conjecture. Zbl 0664.03037Pudlák, Pavel 5 1988 Fragments of bounded arithmetic and the lengths of proofs. Zbl 1168.03044Pudlák, Pavel 5 2008 On the length of proofs of finitistic consistency statements in first order theories. Zbl 0619.03037Pudlák, Pavel 5 1986 The space complexity of cutting planes refutations. Zbl 1388.03055Galesi, Nicola; Pudlák, Pavel; Thapen, Neil 5 2015 Yeast graphs and fermentation of algebraic lattices. Zbl 0358.06013Pudlák, P.; Tůma, J. 4 1976 Distributivity of strongly representable lattices. Zbl 0358.06024Pudlák, Pavel 4 1977 Parity games and propositional proofs. Zbl 1291.03111Beckmann, Arnold; Pudlák, Pavel; Thapen, Neil 4 2014 Twelve problems in proof complexity. Zbl 1142.03369Pudlák, Pavel 4 2008 On convex complexity measures. Zbl 1192.68295Hrubeš, P.; Jukna, S.; Kulikov, A.; Pudlák, P. 4 2010 Every finite lattice can be embedded in the lattice of all equivalences over a finite set. Zbl 0363.06006Pudlak, Pavel; Tuma, Jiri 3 1977 An application of Hindman’s theorem to a problem on communication complexity. Zbl 1088.68612Pudlák, Pavel 3 2003 Circuit lower bounds and linear codes. Zbl 1079.94018Paturi, R.; Pudlák, P. 3 2004 Linear tree codes and the problem of explicit constructions. Zbl 1366.94749Pudlák, Pavel 3 2016 Complexity theory and genetics: The computational power of crossing over. Zbl 1005.68066Pudlák, P. 3 2001 Classification of 8-dimensional trilinear alternating forms over \(\mathrm{GF}(2)\). Zbl 1322.15012Hora, Jan; Pudlák, Petr 3 2015 Kreisel’s conjecture for \(L\exists_ 1\). (Including a postscript by Georg Kreisel). Zbl 0812.03024Baaz, Matthias; Pudlák, Pavel 3 1993 Complexity in mechanized hypothesis formation. Zbl 0404.68097Pudlak, Pavel; Springsteel, Frederick N. 3 1979 Bounded-depth circuits: separating wires from gates (extended abstract). Zbl 1192.68298Koucký, Michal; Pudlák, Pavel; Thérien, Denis 3 2005 Propositional provability and models of weak arithmetic. Zbl 0925.03211Krajíček, Jan; Pudlák, Pavel 3 1990 Bounds for Hodes-Specker theorem. Zbl 0551.03022Pudlák, Pavel 3 1984 On extracting computations from propositional proofs (a survey). Zbl 1245.68089Pudlák, Pavel 3 2010 The complexity of proving that a graph is Ramsey. Zbl 1399.03021Lauria, Massimo; Pudlák, Pavel; Rödl, Vojtěch; Thapen, Neil 3 2017 Consistency and games – in search of new combinatorial principles. Zbl 1105.03059Pudlák, Pavel 2 2006 A bottom-up approach to foundations of mathematics. Zbl 0857.03023Pudlák, Pavel 2 1996 An upper bound for a communication game related to time-space tradeoffs. Zbl 0868.68086Pudlák, Pavel; Sgall, Jiří 2 1997 Abbreviating proofs using metamathematical rules. Zbl 0794.03080Hájek, Petr; Montagna, Franco; Pudlák, Pavel 2 1993 On explicit Ramsey graphs and estimates of the number of sums and products. Zbl 1110.05069Pudlák, Pavel 2 2006 Some relations between subsystems of arithmetic and complexity of computations. Zbl 0752.03029Pudlák, Pavel 2 1992 Extractors for small zero-fixing sources. Zbl 1513.68015Pudlák, Pavel; Rödl, Vojtěch 1 2022 Classification of 9-dimensional trilinear alternating forms over \(\mathrm{GF}(2)\). Zbl 1461.15016Hora, Jan; Pudlák, Petr 1 2021 Random resolution refutations. Zbl 1445.03063Pudlák, Pavel; Thapen, Neil 1 2019 A note on monotone real circuits. Zbl 1422.68115Hrubeš, Pavel; Pudlák, Pavel 2 2018 Beating brute force for (quantified) satisfiability of circuits of bounded treewidth. Zbl 1403.68242Lokshtanov, Daniel; Mikhailin, Ivan; Paturi, Ramamohan; Pudlak, Pavel 1 2018 Incompleteness in the finite domain. Zbl 1423.03245Pudlák, Pavel 9 2017 The complexity of proving that a graph is Ramsey. Zbl 1399.03021Lauria, Massimo; Pudlák, Pavel; Rödl, Vojtěch; Thapen, Neil 3 2017 Tighter hard instances for PPSZ. Zbl 1441.68238Pudlák, Pavel; Scheder, Dominik; Talebanfard, Navid 2 2017 A wild model of linear arithmetic and discretely ordered modules. Zbl 1469.03108Glivický, Petr; Pudlák, Pavel 1 2017 Representations of monotone Boolean functions by linear programs. Zbl 1440.68078de Oliveira Oliveira, Mateus; Pudlák, Pavel 1 2017 Linear tree codes and the problem of explicit constructions. Zbl 1366.94749Pudlák, Pavel 3 2016 Metamathematics of first-order arithmetic. Reprint of the 1993 original published by Springer. Zbl 1365.03008Hájek, Petr; Pudlák, Pavel 2 2016 On the joint entropy of \(d\)-wise-independent variables. Zbl 1413.60003Gavinsky, Dmitry; Pudlák, Pavel 1 2016 On the complexity of finding falsifying assignments for Herbrand disjunctions. Zbl 1378.03043Pudlák, Pavel 7 2015 The space complexity of cutting planes refutations. Zbl 1388.03055Galesi, Nicola; Pudlák, Pavel; Thapen, Neil 5 2015 Classification of 8-dimensional trilinear alternating forms over \(\mathrm{GF}(2)\). Zbl 1322.15012Hora, Jan; Pudlák, Petr 3 2015 Parity games and propositional proofs. Zbl 1291.03111Beckmann, Arnold; Pudlák, Pavel; Thapen, Neil 4 2014 Logical foundations of mathematics and computational complexity. A gentle introduction. Zbl 1270.03001Pudlák, Pavel 10 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 2 2013 Randomness, pseudorandomness and models of arithmetic. Zbl 1432.03067Pudlák, Pavel 2 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 Alternating minima and maxima, Nash equilibria and bounded arithmetic. Zbl 1345.03108Pudlák, Pavel; Thapen, Neil 5 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 A lower bound on the size of resolution proofs of the Ramsey theorem. Zbl 1243.68187Pudlák, Pavel 2 2012 Pseudorandom generators for group products, extended abstract. Zbl 1288.68131Koucký, Michal; Nimbhorkar, Prajakta; Pudlák, Pavel 13 2011 On the complexity of circuit satisfiability. Zbl 1293.68173Paturi, Ramamohan; Pudlak, Pavel 7 2010 Some constructive bounds on Ramsey numbers. Zbl 1200.05137Kostochka, Alexandr; Pudlák, Pavel; Rödl, Vojtech 6 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 3 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 Arithmetic in Prague in the 1970–80s. Zbl 1213.01041Pudlák, Pavel 1 2009 MaLARea SG1 – machine learner for automated reasoning with semantic guidance. Zbl 1165.68434Urban, Josef; Sutcliffe, Geoff; Pudlák, Petr; Vyskočil, Jiří 28 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 2 2006 An improved exponential-time algorithm for \(k\)-SAT. Zbl 1297.68217Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis 59 2005 Bounded-depth circuits: separating wires from gates (extended abstract). Zbl 1192.68298Koucký, Michal; Pudlák, Pavel; Thérien, Denis 3 2005 Pseudorandom sets and explicit constructions of Ramsey graphs. Zbl 1074.05088Pudlák, Pavel; Rödl, Vojtěch 11 2004 Circuit lower bounds and linear codes. Zbl 1079.94018Paturi, R.; Pudlák, P. 3 2004 On reducibility and symmetry of disjoint NP pairs. Zbl 1045.68058Pudlák, Pavel 18 2003 Equilateral sets in \(l_p^n\). Zbl 1034.46015Alon, Noga; Pudlák, Pavel 14 2003 A note on monotone complexity and the rank of matrices. Zbl 1175.68189Gál, Anna; Pudlák, Pavel 6 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 10 2002 Cycles of nonzero elements in low rank matrices. Zbl 0996.05090Pudlák, Pavel 8 2002 Constructive lower bounds for off-diagonal Ramsey numbers. Zbl 0988.05091Alon, Noga; Pudlák, Pavel 9 2001 On the computational content of intuitionistic propositional proofs. Zbl 1009.03027Buss, Samuel R.; Pudlák, Pavel 8 2001 On reducibility and symmetry of disjoint NP-pairs. Zbl 0999.68080Pudlák, Pavel 6 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 26 2000 Some structural properties of low-rank matrices related to computational complexity. Zbl 0938.68059Codenotti, B.; Pudlák, P.; Resta, G. 20 2000 Proofs as games. Zbl 0983.03045Pudlák, Pavel 19 2000 A note on the use of determinant for proving lower bounds on the size of linear circuits. Zbl 1338.68117Pudlák, Pavel 5 2000 Logic colloquium ’98. Proceedings of the annual European summer meeting of the Association for Symbolic Logic, Prague, Czech Republic, August 9–15, 1998. Zbl 0932.00038 1 2000 Satisfiability coding lemma. Zbl 0940.68049Paturi, Ramamohan; Pudlak, Pavel; Zane, Francis 32 1999 Lower bounds for the polynomial calculus and the Gröbner basis algorithm. Zbl 0946.68129Impagliazzo, Russell; Pudlák, Pavel; Sgall, Jiří 27 1999 On the complexity of the propositional calculus. Zbl 0939.03065Pudlák, Pavel 19 1999 A note on applicability of the incompleteness theorem to human mind. Zbl 0923.03013Pudlák, Pavel 1 1999 Metamathematics of first-order arithmetic. 2nd printing. Zbl 0889.03053Hájek, Petr; Pudlák, Pavel 66 1998 The lengths of proofs. Zbl 0920.03056Pudlák, Pavel 43 1998 Some consequences of cryptographical conjectures for \(S_2^1\) and EF. Zbl 0892.68029Krajíček, Jan; Pudlák, Pavel 31 1998 Computing Boolean functions by polynomials and threshold circuits. Zbl 0936.94022Krause, Matthias; Pudlák, Pavel 18 1998 Algebraic models of computation and interpolation for algebraic proof systems. Zbl 0901.03033Pudlák, Pavel; Sgall, Jiří 13 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 92 1997 Boolean circuits, tensor ranks, and communication complexity. Zbl 0870.68068Pudlák, Pavel; Rödl, Vojtěch; Sgall, Jiří 23 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. 21 1997 On the computational power of depth-2 circuits with threshold and modulo gates. Zbl 0908.68110Krause, Matthias; Pudlák, Pavel 20 1997 An upper bound for a communication game related to time-space tradeoffs. Zbl 0868.68086Pudlák, Pavel; Sgall, Jiří 2 1997 On sparse parity check matrices. Zbl 0902.94018Lefmann, Hanno; Pudlák, Pavel; Savický, Petr 2 1997 Lower bounds on Hilbert’s Nullstellensatz and propositional proofs. Zbl 0853.03017Beame, Paul; Impagliazzo, Russell; Krajíček, Jan; Pitassi, Toniann; Pudlák, Pavel 33 1996 On the lengths of proofs of consistency. A survey of results. Zbl 0855.03032Pudlák, Pavel 9 1996 A bottom-up approach to foundations of mathematics. Zbl 0857.03023Pudlák, Pavel 2 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 42 1995 Top-down lower bounds for depth-three circuits. Zbl 0838.68056Håstad, Johan; Jukna, S.; Pudlák, P. 14 1995 How to lie without being (easily) convicted and the lengths of proofs in propositional calculus. Zbl 1044.03542Pudlák, Pavel; Buss, Samuel R. 10 1995 Communication in bounded depth circuits. Zbl 0819.68090Pudlák, P. 25 1994 Superconcentrators of depths 2 and 3; odd levels help (rarely). Zbl 0802.68095Alon, Noga; Pudlak, Pavel 11 1994 On the computational power of depth 2 circuits with threshold and modulo gates. Zbl 1345.68130Krause, Matthias; Pudlák, Pavel 10 1994 Some combinatorial-algebraic problems from complexity theory. Zbl 0824.68053Pudlák, Pavel; Rödl, Vojtěch 10 1994 Unexpected upper bounds on the complexity of some communication games. Zbl 1422.68134Pudlák, Pavel 1 1994 Metamathematics of first-order arithmetic. Zbl 0781.03047Hájek, Petr; Pudlák, Pavel 213 1993 Threshold circuits of bounded depth. Zbl 0801.68052Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György 61 1993 On shifting networks. Zbl 0777.94025Pudlák, Pavel; Savický, Petr 8 1993 Modified ranks of tensors and the size of circuits. Zbl 1310.68119Pudlák, P.; Rödl, V. 6 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 44 1991 Ramsey’s theorem in bounded arithmetic. Zbl 0795.03081Pudlák, Pavel 11 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 28 1990 A lattice of chapters of mathematics (interpretations between theorems). Zbl 0696.03030Mycielski, Jan; Pudlák, Pavel; Stern, Alan S. 18 1990 Lower bounds to the complexity of symmetric Boolean functions. Zbl 0701.68044Babai, L.; Pudlák, P.; Rödl, Vojtěch; Szemeredi, E. 8 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 ...and 30 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 1,278 Authors 31 Buss, Samuel R. 31 Pudlák, Pavel 28 Beyersdorff, Olaf 27 Krajíček, Jan 27 Visser, Albert 22 Jeřábek, Emil 20 Urban, Josef 17 Kołodziejczyk, Leszek Aleksander 14 Thapen, Neil 12 Alon, Noga 12 Hirsch, Edward A. 12 Pitassi, Toniann 11 Atserias, Albert 11 Beckmann, Arnold 11 Galesi, Nicola 11 Impagliazzo, Russell 11 Sherstov, Alexander A. 10 Lauria, Massimo 10 Yukna, Stasys P. 9 Baaz, Matthias 9 Hetzl, Stefan 9 Kurahashi, Taishi 9 Nicolai, Carlo 9 Razborov, Aleksandr Aleksandrovich 9 Servedio, Rocco A. 9 Yokoyama, Keita 8 Göös, Mika 8 Kaliszyk, Cezary 8 Müller, Moritz 8 Willard, Dan E. 7 Aschbacher, Michael George 7 Beklemishev, Lev D. 7 Cordón-Franco, Andrés 7 Ferreira, Fernando 7 Hájek, Petr 7 Lara-Martín, Francisco Felix 7 Pollett, Chris 7 Talebanfard, Navid 7 Todorcevic, Stevo B. 7 Wehrung, Friedrich 6 Adamowicz, Zofia 6 Beimel, Amos 6 Chattopadhyay, Arkadev 6 Cook, Stephen Arthur 6 Enayat, Ali 6 Fernández Margarit, Alejandro 6 Hrubeš, Pavel 6 Itsykson, Dmitry M. 6 Joosten, Joost J. 6 Kabanets, Valentine 6 Nordström, Jakob 6 Pakhomov, Fedor N. 6 Paturi, Ramamohan 6 Rodl, Vojtech 6 Seto, Kazuhisa 6 Shore, Richard Arnold 6 Tůma, Jiří 6 Tzameret, Iddo 6 Urquhart, Alasdair 6 Walsh, Sean 6 Williams, Richard Ryan 6 Zdanowski, Konrad 5 Avigad, Jeremy 5 Bonet, Maria Luisa 5 Chew, Leroy 5 Dean, Walter 5 Dobrinen, Natasha L. 5 Glaßer, Christian 5 Hansen, Kristoffer Arnsfelt 5 Kolokolova, Antonina 5 Maciel, Alexis 5 Papadimitriou, Christos Harilaos 5 Podol’skiĭ, Vladimir Vladimirovich 5 Robere, Robert 5 Sadowski, Zenon 5 Salehi, Saeed 5 Shafer, Paul 5 Slaman, Theodore A. 5 Swanepoel, Konrad J. 5 Tamaki, Suguru 5 Thérien, Denis 5 Wcisło, Bartosz 5 Wegener, Ingo 5 Wigderson, Avi 4 Berarducci, Alessandro 4 Bun, Mark 4 Calabro, Chris 4 Causey, Ryan Michael 4 Cherukhin, Dmitriy Yu. 4 Codenotti, Bruno 4 Cohen, Gil 4 Dantchev, Stefan Stoyanov 4 Esteban, Juan Luis 4 Filmus, Yuval 4 Fischer, Martin 4 Freund, Anton 4 Grigor’ev, Dmitriĭ Yur’evich 4 Hirschfeldt, Denis Roman 4 Jakubův, Jan 4 Kapur, Deepak ...and 1,178 more Authors all top 5 Cited in 165 Serials 109 Annals of Pure and Applied Logic 81 The Journal of Symbolic Logic 70 Theoretical Computer Science 52 Archive for Mathematical Logic 44 Mathematical Logic Quarterly (MLQ) 39 Journal of Computer and System Sciences 31 Computational Complexity 30 Information Processing Letters 27 Algebra Universalis 27 SIAM Journal on Computing 27 Information and Computation 27 The Review of Symbolic Logic 24 The Bulletin of Symbolic Logic 16 Notre Dame Journal of Formal Logic 16 Journal of Automated Reasoning 15 Theory of Computing Systems 13 Discrete Applied Mathematics 13 Transactions of the American Mathematical Society 12 Discrete Mathematics 12 Journal of Algebra 11 Logical Methods in Computer Science 9 Advances in Mathematics 9 Proceedings of the American Mathematical Society 9 Studia Logica 9 Combinatorica 9 Order 8 Journal of Mathematical Sciences (New York) 8 Annals of Mathematics and Artificial Intelligence 8 Journal of Mathematical Logic 7 Artificial Intelligence 7 Journal of Combinatorial Theory. Series A 7 Journal of Symbolic Computation 7 International Journal of Algebra and Computation 7 Linear Algebra and its Applications 7 ACM Transactions on Computational Logic 6 Israel Journal of Mathematics 6 European Journal of Combinatorics 6 Algorithmica 6 SIAM Journal on Discrete Mathematics 6 The Electronic Journal of Combinatorics 5 Journal of Philosophical Logic 5 Formal Methods in System Design 4 Czechoslovak Mathematical Journal 4 Fundamenta Mathematicae 4 Journal of Pure and Applied Algebra 4 Combinatorics, Probability and Computing 4 Theory of Computing 3 Communications in Algebra 3 Mathematical Notes 3 Commentationes Mathematicae Universitatis Carolinae 3 Journal of Functional Analysis 3 Semigroup Forum 3 Journal of Cryptology 3 MSCS. Mathematical Structures in Computer Science 3 International Journal of Foundations of Computer Science 3 Journal of Combinatorial Optimization 3 Journal of the ACM 3 Annals of Mathematics. Second Series 3 Proceedings of the Steklov Institute of Mathematics 3 Mathematics in Computer Science 3 Logica Universalis 2 Russian Mathematical Surveys 2 The Mathematical Intelligencer 2 Algebra and Logic 2 Archiv der Mathematik 2 Bulletin of the London Mathematical Society 2 Journal of Combinatorial Theory. Series B 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 Discrete & Computational Geometry 2 Journal of the American Mathematical Society 2 Forum Mathematicum 2 Random Structures & Algorithms 2 Neural Computation 2 Discrete Mathematics and Applications 2 Mathematical Programming. Series A. Series B 2 Selecta Mathematica. New Series 2 The Journal of Artificial Intelligence Research (JAIR) 2 Soft Computing 2 Interdisciplinary Information Sciences (IIS) 2 Erkenntnis 2 Journal of the Australian Mathematical Society 2 Journal of Applied Logic 2 Forum of Mathematics, Sigma 1 Archiv für Mathematische Logik und Grundlagenforschung 1 Bulletin of the Australian Mathematical Society 1 Journal of Mathematical Analysis and Applications 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 Theory of Probability and its Applications ...and 65 more Serials all top 5 Cited in 39 Fields 646 Mathematical logic and foundations (03-XX) 575 Computer science (68-XX) 150 Combinatorics (05-XX) 116 Order, lattices, ordered algebraic structures (06-XX) 89 Information and communication theory, circuits (94-XX) 50 General algebraic systems (08-XX) 45 Group theory and generalizations (20-XX) 35 Operations research, mathematical programming (90-XX) 23 Linear and multilinear algebra; matrix theory (15-XX) 20 Number theory (11-XX) 20 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 18 Convex and discrete geometry (52-XX) 17 Functional analysis (46-XX) 15 Probability theory and stochastic processes (60-XX) 12 History and biography (01-XX) 11 General topology (54-XX) 10 General and overarching topics; collections (00-XX) 9 Commutative algebra (13-XX) 9 Geometry (51-XX) 6 Field theory and polynomials (12-XX) 6 Numerical analysis (65-XX) 6 Quantum theory (81-XX) 4 Algebraic geometry (14-XX) 4 Associative rings and algebras (16-XX) 4 Category theory; homological algebra (18-XX) 3 Statistics (62-XX) 3 Biology and other natural sciences (92-XX) 2 Real functions (26-XX) 2 Operator theory (47-XX) 1 Nonassociative rings and algebras (17-XX) 1 \(K\)-theory (19-XX) 1 Topological groups, Lie groups (22-XX) 1 Measure and integration (28-XX) 1 Functions of a complex variable (30-XX) 1 Special functions (33-XX) 1 Difference and functional equations (39-XX) 1 Abstract harmonic analysis (43-XX) 1 Algebraic topology (55-XX) 1 Global analysis, analysis on manifolds (58-XX) Citations by Year