[1] P. Pudlak: Observational predicate calculus and complexity of
computations,
Comm. Math. Univ. Carol. Vol.16, 1975, No.2, pp.395-398.
[2] P. Pudlak: A new proof of the congruence lattice
representation
theorem,
Algebra Universalis, Vol.6, 1976, pp.269-275.
[3] P. Pudlak: Distributivity of strongly representable lattices,
Algebra
Universalis, Vol.7, 1977, pp.85-92
[4] P. Pudlak, F.N. Springsteal: Complexity in mechanized
hypothesis
formation,
Theor. Comp. Sci. Vol.8, 1979, pp.203-225.
[5] P. Pudlak: Symmetric embeddings of finite lattices into
finite
partition
lattices, Comm. Math. Univ. Carol. Vol.20, 1979, pp.183-187.
[6] P. Pudlak, J. Tuma: Every finite lattice can be embedded in a
finite
partition lattice, Algebra Universalis, Vol.10, 1980, pp.74-95.
[7] P. Pudlak, P.P. Palfy: Congruence lattices of finite algebras
and
intervals
in subgroup lattices of finite groups, Algebra Universalis, Vol.11,
1980,
pp.22-27.
[8] S. Poljak, P. Pudlak, D. Turzik: Extension of k-subsets to
k+1-subsets
- existence versus constructibility, Comm. Math. Univ. Carol., Vol.23,
1982, pp.337-349.
[9] P. Pudlak, V. Rodl: Partition theorems for systems of finite
subsets
of integers. Discrete Math., Vol.39, 1982, pp.67-73.
[10] P. Pudlak: Some prime elements in the lattice of
interpretability
types, Trans. A.M.S., Vol.280, 1983, No.1, pp.225-275.
[11] P. Pudlak: A definition of exponentiation by a bounded
arithmetical
formula, Comm. Math. Univ. Carol. Vol.24, 1983 No.4 pp.667-671.
[12] P. Pudlak, J. Tuma: Regraphs and congruence lattices,
Algebra
Universalis
Vol.17, 1984, pp.416-424.
[13] P. Pudlak A. Sochor: Models of the Alternative Set Theory,
Journ.
Sym. Logic Vol.49, 1984 No.2 pp.570-585.
[14] P. Pudlak A. Sochor: Elementary extensions of models of the
Alternative
Set Theory, Zeitschrift. fur Math. Logik, Vol.31, 1985 pp.309-316.
[15] P. Pudlak: On congruence lattices of lattices, Algebra
Universalis
Vol.20, 1985, pp.96-114.
(correction)
[16] P. Pudlak: Cuts, consistency statements and interpretations,
Journ.
Symb. Logic Vol.50, 1985, pp.423-441.
[17] J. Krajicek, P. Pudlak: The number of proof lines and the
size of
proofs in first order logic, Arch. Math. Log. Vol.27, 1988 pp.69-84.
[18] P. Pudlak, V. Rodl, P. Savicky: Graph complexity, Acta
Informatica,
Vol.25, 1988 pp.515-535.
[19] P. Pudlak: On a unification problem related to Kreisel's
conjecture,
Comm. Math. Univ. Carol., Vol 29,3, 1988 pp.551-556.
[20] J. Krajicek, P. Pudlak: Propositional proof systems, the
consistency
of first order theories and the complexity of computations, JSL Vol.54,
No.3, 1989, pp.1063-1079.
[21] J. Krajicek, P. Pudlak:On the structure of initial segments
of
models
of arithmetic, Arch. Math. Log. Vol.28, 1989, pp.91-98.
[22] J. Mycielski, P. Pudlak, A.S. Stern: A lattice of chapters
of
mathematics,
Memoirs AMS, Vol.84, No.426, 1990, 70 pp.
[23] J. Krajicek, P. Pudlak: Quantified propositional calculi and
fragments
of bounded arithmetic, Zeitschrift fur Math. Logik 36, 1990, pp.29-46.
[24] Babai L. P. Pudlak V. Rodl Szemeredi E.: Lower bounds to the
complexity
of symmetric boolean functions, Theor. Comp. Sci. 74, 1990, pp.313-323.
[25] P. Pudlak: A note on bounded arithmetic, Fundamenta
Mathematicae,
Vol.136, No.2, 1990, pp.86-89.
[26] Jezek J. P. Pudlak Tuma J.: On eqational theories of
semilattices
with operators, Bull. Austral. Math. Soc.42, (1990), pp.57-70.
[27] J. Krajicek, P. Pudlak Takeuti G.: Bounded arithmetic and
polynomial
hierarchy, Annals of Pure and Applied Logic 52,(1991), pp.143-154.
[28] P. Pudlak V. Rodl: A combinatorial approach to complexity,
Combinatorica
Vol.12(2), 1992, pp.221-226.
[29] P. Pudlak Vavri n Z.: Computation of rigidity of order n/r
for one simple matrix, Comm. Math. Univ. Carol. 32,2 (1991), pp.213-218.
[30] P. Pudlak Savicky P.: On shifting networks, Theor. Comput.
Sci.
Vol.116,
1993, pp.415-419.
[31] Hajnal A. Maass W. P. Pudlak Szegedy M. Turan G.: Threshold
circuits
of bounded depth. Journ. of Comput. and System Science 46 (1993),
pp.129-154.
[33] Alon N. P. Pudlak: Superconcentrators of depth 2 and 3; odd
levels
help (rarely), Journ. of Computer and System Sciences 48,1 (1994),
pp.194-202.
[34] P. Pudlak V. Rodl: Some combinatorial-algebraic problems
from
complexity
theory, Discrete Math. 136 (1994), pp.253-279.
[35] J. Krajicek,, P. Pudlak, 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.
[36] Hastad J., Jukna S., P. Pudlak: 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).
[37] Beam P., Impagliazzo R., J. Krajicek,, Pitassi T., P.
Pudlak:
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).
[38] P. Pudlak, V. Rodl, Sgall J.: Boolean circuits, tensor ranks
and
communication
complexity, SIAM J. on Computing 26/3 (1997), pp.605-633.
[40] Lefmann H., P. Pudlak, Savicky P: On
sparse parity check matrices, Codes, Designes and Cryptography 12,
pp.107-130 (abstract published in Proc. COCOON 96).
[42] Buss S., Impagliazzo R., J. Krajicek, P. Pudlak, 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
[43] Krause M., P. Pudlak: 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.
[45]
Impagliazzo R., P. Pudlak, Sgall J.: Lower bounds for the polynomial
calculus and the Groebner basis algorithm. Comput. Complexity, 8(2)
(1999), pp. 127-144. (
ECCC TR97-043)
[46] P. Pudlak, 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
[48] P. Pudlak: 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)
[49] P. Pudlak: Proofs
as games , American Math. Monthly, June-July 2000, pp.541-550.
[53] P. Pudlak: 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)
[54] N. Alon , P. Pudlak: Equilateral
sets in l_p, Geometric and Functional Analysis 13 (2003), pp.
467-482.
[55] A. Atserias, N. Galesi , P. Pudlak: 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)
[60] R. Paturi, P. Pudlak, 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)
[61] P. Pudlak: Quantum deduction
rules, Annals of Pure and Applied Logic 157 (2009), pp.16-29. [k]
[1] P. Pudlak Tuma J.: Yeast graphs and fermentation of algebraic
lattices.
In: Coll. Math. Soc. Janos Bolyai, 14. Lattice Theory, Szeged, 1974
pp.301-341.
[2] P. Pudlak: Generalized quantifiers and semisets In: Set
Theory and
Hierarchy Theory, Karpacz, Wroc\l aw Technical Univ. 1974 pp.109-116.
[3] P. Pudlak: Polynomially complete problems in the logic of
automated
discovery. In: Math. Found. of Comp. Sci., LNCS 32, Springer-Verlag,
1975,
pp.395-398.
[4] Hajek P. P. Pudlak: 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.
[5] J. Moravek, P. Pudlak: New lower bound for polyhedral
membership
problem.
In:Proceedings of MFCS'84 LNCS 176, Springer-Verlag, 1984 pp.416-424..
[6] P. Pudlak: Bounds for Hodes-Specker theorem. In: Logic and
Machines
LNCS 171, Springer Verlag, 1984 pp.421-445.
[7] P. Pudlak: A lower bound on the complexity of branching
programs.
In:
Proc. MFCS'84 LNCS 176, Springer-Verlag, 1984 pp.480-489.
[8] M. Ajtai , L. Babai , P. Hajnal , J. Komlos, P. Pudlak V.
Rodl: Two
lower bounds for branching programs. In:Proc. 18-th ACM STOC, 1986
pp.30-38.
[9] P. Pudlak: 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.
[10] P. Pudlak: Improved bounds to the length of proofs of
finitistic
consistency
statements. In: Contemporary mathematics Vol.65, 1987 pp.309-331.
[11] A. Hajnal , W. Maass, P. Pudlak, 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 [31])
[12] P. Duris, P. Pudlak: On the communication complexity of
planarity.
In: Fundamentals of Comp. Theor. '89, Springer-Verlag LNCS 380, 1989,
pp.145-147.
[13] J. Krajicek, P. Pudlak: 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.
[14] J. Krajicek, P. Pudlak, J. Sgall : Interactive computations
of
optimal
solutions. In: Proc. MFCS'90, Ed. B.Rovan, Springer-Verlag LNCS 452,
1990,
pp.48-60.
[15] P. Pudlak: Boolean complexity and Ramsey theorems. In:
Mathematics
of Ramsey Theory, J.Nesetril and V.Rodl Eds., 1991, pp.246-252.
[16] P. Pudlak: Ramsey's Theorem in Bounded Arithmetic. In: Proc.
Computer
Science Logic'90, eds. E.Borger, H.Kleine Buning, M.M.Richter,
W.Schonfeld,
LNCS 553, Springer-Verlag, 1991, pp.308-317.
[17] J. Nesetril, P. Pudlak: A note on boolean dimension of
posets. In:
Proc. Irregularities of Partitions, Hungary.
[18] P. Pudlak: Some relations between subsystems of arithmetic
and the
complexity theory, Proc. Conf. Logic from Computer Science,
Springer-Verlag
1992, pp.499-519.
[19] P. Beam, R. Impagliazzo, J. Krajicek, T. Pitassi, P. Pudlak,
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.
[20] M. Baaz, P. Pudlak:
Kreisel's conjecture for LE1, in: Arithmetic Proof
Theory and Computational Complexity, eds. P. Clote and J. Krajicek,
Oxford Univ. Press 1993, pp.30-49.
[21] P. Hajek , F. Montagna, P. Pudlak: 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.
[22] P. Pudlak, V. Rodl: Modified ranks of tensors and the size
of
circuits,
in Proc. ACM STOC, 1993, pp.523-531.
[24] J. Krajicek, P. Pudlak: Some consequences of cryptographical
conjectures
for S21 and EF, in Logic and
Computational
Complexity, (procedings of meeting held in Indianapolis 1994), Ed. D.
Leivant,
Springer LNCS 960, 1995, pp.210-220.
[25] P. Pudlak, 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.
[26] P. Pudlak, 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
[27] B. Codenotti, P. Gemmell, J. Simon, P. Pudlak: On the amount
of
randomness
needed in distributed computations, in Proc. OPODIS'97 , 1997, pp.
237-248
[32] R. Paturi, P. Pudlak: 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.
[35] A. Chattopadhyay, N. Goyal, P. Pudlak, 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]
[1] P. Pudlak: The hierarchy of boolean circuits, Computers and
AI,
Vol.6,
1987 pp.449-468.
[2] P. Pudlak: AC0 circuit complexity. In:
Proc.
FCT,
1993, pp.106-120.
[3] P. Pudlak: Unexpected upper bounds on the complexity of some
communication
games, in Proc. ICALP 1994,Springer-Verlag LNCS 820, pp.1-10.
[4] P. Pudlak: 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.
[5] P. Pudlak: 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.
[9] P. Pudlak: 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