Bibliography of Pavel Pudlák

Books

P. Hájek, P. Pudlák: Metamathematics of first order arithmetic, Springer-Verlag/ASL Pespectives in Logic, 1993, 460 pp. (corrections)
P. Pudlák: Logical Foundations of Mathematics and Computational Complexity, a gentle introduction. Springer-Verlag, 2013, 695 pp. ( preface and table of contents)

Papers in journals

P. Pudlák: Observational predicate calculus and complexity of computations, Comm. Math. Univ. Carol. Vol.16, 1975, No.2, pp.395-398.
P. Pudlák: A new proof of the congruence lattice representation theorem, Algebra Universalis, Vol.6, 1976, pp.269-275.
P. Pudlák: Distributivity of strongly representable lattices, Algebra Universalis, Vol.7, 1977, pp.85-92
P. Pudlák, F.N. Springsteal: Complexity in mechanized hypothesis formation, Theor. Comp. Sci. Vol.8, 1979, pp.203-225.
P. Pudlák: Symmetric embeddings of finite lattices into finite partition lattices, Comm. Math. Univ. Carol. Vol.20, 1979, pp.183-187.
P. Pudlák, J. Tuma: Every finite lattice can be embedded in a finite partition lattice, Algebra Universalis, Vol.10, 1980, pp.74-95.
P. Pudlák, P.P. Palfy: Congruence lattices of finite algebras and intervals in subgroup lattices of finite groups, Algebra Universalis, Vol.11, 1980, pp.22-27.
S. Poljak, P. Pudlák, D. Turzik: Extension of k-subsets to k+1-subsets - existence versus constructibility, Comm. Math. Univ. Carol., Vol.23, 1982, pp.337-349.
P. Pudlák, V. Rodl: Partition theorems for systems of finite subsets of integers. Discrete Math., Vol.39, 1982, pp.67-73.
P. Pudlák: Some prime elements in the lattice of interpretability types, Trans. A.M.S., Vol.280, 1983, No.1, pp.225-275.
P. Pudlák: A definition of exponentiation by a bounded arithmetical formula, Comm. Math. Univ. Carol. Vol.24, 1983 No.4 pp.667-671.
P. Pudlák, J. Tuma: Regraphs and congruence lattices, Algebra Universalis Vol.17, 1984, pp.416-424.
P. Pudlák A. Sochor: Models of the Alternative Set Theory, Journ. Sym. Logic Vol.49, 1984 No.2 pp.570-585.
P. Pudlák A. Sochor: Elementary extensions of models of the Alternative Set Theory, Zeitschrift. fur Math. Logik, Vol.31, 1985 pp.309-316.
P. Pudlák: On congruence lattices of lattices, Algebra Universalis Vol.20, 1985, pp.96-114. (correction)
P. Pudlák: Cuts, consistency statements and interpretations, Journ. Symb. Logic Vol.50, 1985, pp.423-441.
J. Krajicek, P. Pudlák: The number of proof lines and the size of proofs in first order logic, Arch. Math. Log. Vol.27, 1988 pp.69-84.
P. Pudlák, V. Rodl, P. Savicky: Graph complexity, Acta Informatica, Vol.25, 1988 pp.515-535.
P. Pudlák: On a unification problem related to Kreisel's conjecture, Comm. Math. Univ. Carol., Vol 29,3, 1988 pp.551-556.
J. Krajicek, P. Pudlák: Propositional proof systems, the consistency of first order theories and the complexity of computations, JSL Vol.54, No.3, 1989, pp.1063-1079.
J. Krajicek, P. Pudlák:On the structure of initial segments of models of arithmetic, Arch. Math. Log. Vol.28, 1989, pp.91-98.
J. Mycielski, P. Pudlák, A.S. Stern: A lattice of chapters of mathematics, Memoirs AMS, Vol.84, No.426, 1990, 70 pp.
J. Krajicek, P. Pudlák: Quantified propositional calculi and fragments of bounded arithmetic, Zeitschrift fur Math. Logik 36, 1990, pp.29-46.
Babai L. P. Pudlák V. Rodl Szemeredi E.: Lower bounds to the complexity of symmetric boolean functions, Theor. Comp. Sci. 74, 1990, pp.313-323.
P. Pudlák: A note on bounded arithmetic, Fundamenta Mathematicae, Vol.136, No.2, 1990, pp.86-89.
Jezek J. P. Pudlák Tuma J.: On eqational theories of semilattices with operators, Bull. Austral. Math. Soc.42, (1990), pp.57-70.
J. Krajicek, P. Pudlák Takeuti G.: Bounded arithmetic and polynomial hierarchy, Annals of Pure and Applied Logic 52,(1991), pp.143-154.
P. Pudlák V. Rodl: A combinatorial approach to complexity, Combinatorica Vol.12(2), 1992, pp.221-226.
P. Pudlák Vavri n Z.: Computation of rigidity of order n/r for one simple matrix, Comm. Math. Univ. Carol. 32,2 (1991), pp.213-218.
P. Pudlák Savicky P.: On shifting networks, Theor. Comput. Sci. Vol.116, 1993, pp.415-419.
Hajnal A. Maass W. P. Pudlák Szegedy M. Turan G.: Threshold circuits of bounded depth. Journ. of Comput. and System Science 46 (1993), pp.129-154.
P. Pudlák: Communication in bounded depth circuits, Combinatorica 14 (2) (1994), pp.203-216.
Alon N. P. Pudlák: Superconcentrators of depth 2 and 3; odd levels help (rarely), Journ. of Computer and System Sciences 48,1 (1994), pp.194-202.
P. Pudlák V. Rodl: Some combinatorial-algebraic problems from complexity theory, Discrete Math. 136 (1994), pp.253-279.
J. Krajicek,, P. Pudlák, Woods A.: Exponential lower bound to the size of bounded depth Frege proofs of the Pigeon Hole Principle, Random Structures and Algorithms, 7/1 (1995), pp.15-39.
Hastad J., Jukna S., P. Pudlák: Top-down lower bounds for depth-three circuits, Computational Complexity 5 (1995), pp.99-112 (extended abstract appeared in Proc. IEEE FOCS, 1993, pp.124-129).
Beam P., Impagliazzo R., J. Krajicek,, Pitassi T., P. Pudlák: Lower bounds on Hilbert's Nullstellensatz and propositional proofs, Proc. London Math. Soc. (3) 73 (1996), pp.1-26, (preliminary version in IEEE Proc. FOCS, 1994).
P. Pudlák, V. Rodl, Sgall J.: Boolean circuits, tensor ranks and communication complexity, SIAM J. on Computing 26/3 (1997), pp.605-633.
P. Pudlák: Lower bounds for resolution and cutting planes proofs and monotone computations, J. of Symb. Logic 62(3), 1997, pp.981-998.
Lefmann H., P. Pudlák, Savicky P: On sparse parity check matrices, Codes, Designes and Cryptography 12, pp.107-130 (abstract published in Proc. COCOON 96).
Krause M., P. Pudlák: On the computational power of depth 2 circuits with threshold and modulo gates, Theoretical Computer Science 174 (1997), pp.137-156, (preliminary version in Proc. ACM STOC, 1994, pp.48-57)
Buss S., Impagliazzo R., J. Krajicek, P. Pudlák, A.A. Razborov J. Sgall: Proof Complexity in Algebraic Systems and constant depth Frege systems with a modular counting connective, Computational Complexity 6 (1996/97), pp. 256-298
Krause M., P. Pudlák: Computing Boolean Functions by Polynomials and Threshold Circuits, Computational Complexity 7 (1998), pp. 346-370, preliminary version: On computing boolean functions by sparse real polynomials, appeared in Proc. IEEE FOCS 1995, pp.682-691.
P. Pudlák: A note on applicability of the incompleteness theorem to human mind, Annals of Pure and Applied Logic 96 (1999), pp. 335-342 (pdf)
Impagliazzo R., P. Pudlák, Sgall J.: Lower bounds for the polynomial calculus and the Groebner basis algorithm. Comput. Complexity, 8(2) (1999), pp. 127-144. ( ECCC TR97-043)
P. Pudlák, Paturi R., Zane F.: Satisfiability coding lemma. Chicago Journal of Theoretical Computer Science, December 1999. Preliminary version in Proc. 38-th FOCS, IEEE Computer Society 1997, pp. 566-574
Codenotti B., P. Pudlák, Resta J.: Some structural properties of low rank matrices related to computational complexity Theoretical Computer Sci. 235 (2000), pp. 89-107 ( ECCC TR97-043)
P. Pudlák: A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits. Information Processing Letters 74 (2000), pp.197-201. ( ECCC TR98-042)
P. Pudlák: Proofs as games , American Math. Monthly, June-July 2000, pp.541-550.
P. Pudlák: Cycles of nonzero elements in low rank matrices , Combinatorica 22 (2), 2002, pp.321-334 (correction)
N. Alon, P. Pudlák: Constructive lower bounds for off-diagonal Ramsey numbers, Israel Journ. of Math. 122 (2001), pp.243-251.
S. Buss, P. Pudlák: On the computational content of intuitionistic propositional proofs Annals of Pure and Applied Logic 109 (2001), pp. 49-64.
P. Pudlák: Complexity theory and genetics: The computational power of crossing over, Information and Computation 171, (2001), pp.201-223; preliminary version appeared in IEEE Proc. Structure in Complexity Theory 1994, pp.383-395. (here is an extended version in postscript and pdf)
N. Alon , P. Pudlák: Equilateral sets in l_p, Geometric and Functional Analysis 13 (2003), pp. 467-482.
A. Atserias, N. Galesi , P. Pudlák: Monotone simulations of nonmonotone proofs, J. of Computer and System Sciences 65 (2002), pp.626-638, (preliminary version in Proc. 16th IEEE Conf. on Computational Complexity 2001, 36-41)
P. Pudlák: On reducibility and symmetry of disjoint NP-pairs, Theor. Comput. Science 295 (2003) 323-339, preliminary version in Proc. MFCS'01, 2001.
P. Pudlák: An application of Hindman's theorem to a problem on communication complexity, Combinatorics, Probability and Computing (2003) 12, pp. 661-670.
A. Gal , P. Pudlák: Monotone complexity and the rank of matrices, Information Processing Letters 87 (2003), pp. 321-326.
P. Pudlák: Parallel strategies, J. of Symb. Logic 68(4), 2003, pp.1242-1250.
R. Paturi, P. Pudlák, M.E.Saks, F. Zane: An improved exponential-time algorithm for k-SAT, Journal of the ACM Vol.52, No.3, 2005, pp.337-364 (preliminary version in Proc. 39-th FOCS, IEEE 1998, pp. 628-637)
P. Pudlák: Quantum deduction rules, Annals of Pure and Applied Logic 157 (2009), pp.16-29. [k]
P. Pudlák: Fragments of Bounded Arithmetic and the lengths of proofs, Journal of Symbolic Logic 73/4 (2008), pp. 1389-1406. [a]
P. Hrubes, A. Kulikov, P. Pudlák, S. Jukna: On convex complexity measures, Theoretical Computer Science 411 (2010), pp.1842-1854. [a]
A. Kostochka, P. Pudlák, V. Rodl: Some constructive bounds on Ramsey numbers, Journal of Combinatorial Theory, Series B 100 (2010), pp. 439-445. [k,m]
P. Pudlák, N. Thapen: Alternating minima and maxima, Nash equilibria and Bounded Arithmetic, Annals of Pure and Applied Logic 163 (2012), pp. 604-614. [a]
P. Pudlák: A lower bound on the size of resolution proofs of the Ramsey theorem, Information Processing Letters 112 (14-15), 2012, pp. 610-611. [a,i]

Papers in proceedings

P. Pudlák, J. Tuma: Yeast graphs and fermentation of algebraic lattices. In: Coll. Math. Soc. Janos Bolyai, 14. Lattice Theory, Szeged, 1974 pp.301-341.
P. Pudlák: Generalized quantifiers and semisets In: Set Theory and Hierarchy Theory, Karpacz, Wroc\l aw Technical Univ. 1974 pp.109-116.
P. Pudlák: Polynomially complete problems in the logic of automated discovery. In: Math. Found. of Comp. Sci., LNCS 32, Springer-Verlag, 1975, pp.395-398.
P. Hajek, P. Pudlák: Two orderings of the class of all countable models of arithmetic. In: Model Theory of Algebra and Arithmetic, LNM 843, Springer-Verlag, 1980, pp.174-185.
J. Moravek, P. Pudlák: New lower bound for polyhedral membership problem. In:Proceedings of MFCS'84 LNCS 176, Springer-Verlag, 1984 pp.416-424..
P. Pudlák: Bounds for Hodes-Specker theorem. In: Logic and Machines LNCS 171, Springer Verlag, 1984 pp.421-445.
P. Pudlák: A lower bound on the complexity of branching programs. In: Proc. MFCS'84 LNCS 176, Springer-Verlag, 1984 pp.480-489.
M. Ajtai , L. Babai , P. Hajnal , J. Komlos, P. Pudlák V. Rodl: Two lower bounds for branching programs. In:Proc. 18-th ACM STOC, 1986 pp.30-38.
P. Pudlák: On the length of proofs of finitistic consistency statements in first order theories. In: Logic Colloquium 84, North Holland P.C., 1986 pp.165-196.
P. Pudlák: Improved bounds to the length of proofs of finitistic consistency statements. In: Contemporary mathematics Vol.65, 1987 pp.309-331.
A. Hajnal , W. Maass, P. Pudlák, M. Szegedy, G. Turan G: Threshold circuits of bounded depth. In: Proc. 28-th IEEE STOC, 1987 pp.99-110. (preliminary version of the journal article)
P. Duris, P. Pudlák: On the communication complexity of planarity. In: Fundamentals of Comp. Theor. '89, Springer-Verlag LNCS 380, 1989, pp.145-147.
J. Krajicek, P. Pudlák: Propositional provability and models of weak arithmetic. In: Proc. Computer Science Logic'89, Eds. Borger, Kleine-Buning, Richter, Springer-Verlag LNCS 440, 1990, pp.193-210.
J. Krajicek, P. Pudlák, J. Sgall : Interactive computations of optimal solutions. In: Proc. MFCS'90, Ed. B.Rovan, Springer-Verlag LNCS 452, 1990, pp.48-60.
P. Pudlák: Boolean complexity and Ramsey theorems. In: Mathematics of Ramsey Theory, J.Nesetril and V.Rodl Eds., 1991, pp.246-252.
P. Pudlák: Ramsey's Theorem in Bounded Arithmetic. In: Proc. Computer Science Logic'90, eds. E.Borger, H.Kleine Buning, M.M.Richter, W.Schonfeld, LNCS 533, Springer-Verlag, 1991, pp.308-317.
J. Nesetril, P. Pudlák: A note on boolean dimension of posets. In: Proc. Irregularities of Partitions, Hungary.
P. Pudlák: Some relations between subsystems of arithmetic and the complexity theory, Proc. Conf. Logic from Computer Science, Springer-Verlag 1992, pp.499-519.
P. Beam, R. Impagliazzo, J. Krajicek, T. Pitassi, P. Pudlák, A. Woods : Exponential lower bound to the size of bounded depth Frege proofs of the Pigeon Hole Principle, in Proc. ACM STOC, 1992, pp.200-220.
M. Baaz, P. Pudlák: Kreisel's conjecture for LE₁, in: Arithmetic Proof Theory and Computational Complexity, eds. P. Clote and J. Krajicek, Oxford Univ. Press 1993, pp.30-49.
P. Hajek , F. Montagna, P. Pudlák: Abbreviating proofs using metamathematical rules, in Arithmetic Proof Theory and Computational Complexity, eds. P. Clote and J. Krajicek, Oxford Univ. Press 1993, pp.197-221.
P. Pudlák, V. Rodl: Modified ranks of tensors and the size of circuits, in Proc. ACM STOC, 1993, pp.523-531.
P. Pudlák, S.R. Buss: How to lie without being (easily) convicted and the lengths of proofs in proposotional claculus, in Computer Science Logic'94, Pacholski and Tiuryn eds., Springer-Verlag LNCS 933, 1995, pp.151-162.
J. Krajicek, P. Pudlák: Some consequences of cryptographical conjectures for S₂¹ and EF, in Logic and Computational Complexity, (procedings of meeting held in Indianapolis 1994), Ed. D. Leivant, Springer LNCS 960, 1995, pp.210-220.
P. Pudlák, J. Sgall: An upper bound for a communication game related to space-time trade-offs, in Mathematics of Paul Erdos, R.L. Graham and J. Nesetril eds., Vol I., Springer-Verlag 1997, pp.393-399.
P. Pudlák, J. Sgall: Algebraic models of computations and interpolation for algebraic proof systems, in Proof Complexity and Feasible Arithmetic, ed. S. Buss, LNCS, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 39, 1998, pp. 279-295
B. Codenotti, P. Gemmell, J. Simon, P. Pudlák: On the amount of randomness needed in distributed computations, in Proc. OPODIS'97 , 1997, pp. 237-248
P. Pudlák: On the complexity of propositional calculus. Sets and Proofs, Invited papers from Logic Colloquium'97, Cambridge Univ. Press 1999, pp. 197-218
R. Impagliazzo, P. Pudlák: A lower bound for DLL algorithms for k-SAT, SODA 2000, pp. 128-136
P. Pudlák: Consistency and games - in search of new combinatorial principles. Proc. Logic Colloquium'03, Helsinki, eds. V. Stoltenberg-Hansen and J. Vaananen, Assoc. for Symbolic Logic 2006, pp.244-281
P. Pudlák, V. Rodl: Pseudorandom sets and explicit constructions of Ramsey graphs. Quaderni di Matematica, Vol. 13, Dipartimanto di Matematica, Seconda Universita di Napoli, Caserta - 2004, editor J. Krajicek, pp.327-346
R. Paturi, P. Pudlák: Circuit lower bounds and linear codes. Notes of Mathematical Seminars of St.Petersburg Department of Steklov Institute of Mathematics, vol. 316, Teoria slozhnosti vychislenij IX, E. A. Hirsch editor, 2004, pp.188-204.
M. Koucky, P. Pudlák, D. Therien: Bounded depth circuits: separating wires from gates. In Proc. 37th Annual ACM Symp. on Theory of Computing, 2005, pp.257-265
P. Pudlák: On explicit Ramsey graphs and estimates of the number of sums and products. Topics in Discrete Mathematics, editors Klazar, Kratochvil, Loebl, Matousek, Thomas and Valter. Springer 2006, pp.169-175[a]
A. Chattopadhyay, N. Goyal, P. Pudlák, D. Therien: Lower bounds for circuits with MOD_m gates, Proc. 47th Annual Symp. on Foundations of Computer Science, IEEE 2006, pp.709-718 [a]
D. Gavinsky, P. Pudlák: Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity, Proc. 23rd Annual IEE Conference on Computational Complexity, 2008, pp. 332-339.[a,m]
V. Cacic, P. Pudlák, G. Restall, A. Visser, A. Urquhart: Decorated linear order types and the theory of concatenation, Proc. Logic Colloquium 2007, ASL Lecture Notes in Logic, Cambridge 2010, pp. 1-13 [m,u]
R. Paturi, P. Pudlák: On the complexity of circuit satisfiability, Proc. of the 2010 ACM STOC, pp. 241-249 [a,m,u]
M. Koucky, P. Nimbhorkar, P. Pudlák: Pseudorandom Generators for Group Products, Proc. of the 2011 ACM STOC, pp. 263-272. [a,m,u]
A. Gál, K.A. Hansen, M. Koucký, P. Pudlák, and E. Viola. Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. 44th Annual ACM Symposium on Theory of Computing, STOC'12, pp. 479-494, 2012.

Surveys and general expositions

P. Pudlák: The hierarchy of boolean circuits, Computers and AI, Vol.6, 1987 pp.449-468.
P. Pudlák: AC⁰ circuit complexity. In: Proc. FCT, 1993, pp.106-120.
P. Pudlák: Unexpected upper bounds on the complexity of some communication games, in Proc. ICALP 1994,Springer-Verlag LNCS 820, pp.1-10.
P. Pudlák: Logic and Complexity: Independence results and the complexity of propositional calculus, in Proc. Internat. Congress of Math., Zurich, 1994 (45 min. invited lecture), pp.288-297.
P. Pudlák: A bottom-up approach to foundations of mathematics, in Proc. Godel'96, Logical Foundations of Mathematics, Computer Science and Physics -- Kurt Godel's Legacy, P. Hajek ed., Springer Lecture Notes in Logic 6, pp.81-97.
P. Pudlák: On the lengths of proofs of consistency, Collegium Logicum, Annals of the Kurt-Godel-Society, Vol. 2, 1996, pp.65-86.
P. Pudlák: The lengths of proofs, in Handbook of Proof Theory, S.R. Buss ed., Elsevier, 1998, pp.547-637.
P. Pudlák: Satisfiability - Algorithms and Logic, in Mathematical Foundations of Computer Science 1998, Springer LNCS 1450, pp.129-141.
P. Pudlák: Godel and computations, Proc. 21st IEEE Conference on Computational Complexity, 2006, pp.3-5, full version in ACM SIGACT News Vol. 37/4 (2006) pp.13-21
P. Pudlák: Twelve problems in proof complexity, Proc. 3rd International Computer Science Symposium in Russia, CSR 2008, pp.13-27[a,m,k]
P. Pudlák: On extracting computations from propositional proofs Proc. Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Chennai, 2010, Leibnitz International Proceedings in Informatics.

Technical reports, unpublihshed papers, submitted papers

P. Pudlák: Another combinatorial sentence independent of Peano's axioms, 5 pp.
P. Pudlák, S. Zak: Space complexity of computations, Math. Inst., CSAV, Prague, 1983, 30 pp.
T. Hofmeister, P. Pudlák: A proof that division is not in TC₂⁰, Univ. Dortmund, Research Rep. No. 447, 1992, 5 pp.
Pavel Pudlák, Petr Pudlák: Does dominance-recessiveness have a survival value?
P. Pudlák: A nice choice function in a countable model
P. Pudlák: A nonlinear bound on the number of wires in bounded depth circuits,2005, ECCC TR05-122
P. Pudlák: Superexponential computations in exponential domain (Extended abstract of a lecture at JAF, Seville 11.6.2007)
P. Pudlák: Randomness, pseudorandomness and models of arithmetic. arXiv:1210.4692