### Jan Krajicek - Publications#

Books:
• Bounded arithmetic, propositional logic, and complexity theory, Cambridge University Press, 1995.
• Forcing with random variables and proof complexity, Cambridge University Press, 2011.
• Proof complexity, Cambridge University Press, to appear.

Edited volumes:
• with P. Clote, Arithmetic, Proof Theory and Computational Complexity, Oxford University Press, 1993.
• Complexity of computations and proofs, Quaderni di Matematica, Vol.13, ser. published by Seconda Universita di Napoli, Caserta, 2004.
• with M. Baaz and S. Friedman, Logic Colloquium'01, Proc. of the European ASL meeting in Vienna 2001, Lecture Notes in Logic, Vol.20, Assoc. for Symb. Logic, A K Peters, Ltd., and Wellesley (Mass.US), 2005.

Research papers:
• Some Theorems on the Lattice of Local Interpretability Types, Zeitschr. f. Mathematikal Logik u. Grundlagen d. Mathematik, Bd. 31, (1985), pp. 449-460.
• A Possible Modal Formulation of Comprehension Scheme, Zeitchr. f. Mathematikal Logik u. Grundlagen d. Mathematik, Bd.33(5), (1987), pp. 461-480.
• Some Results and Problems in the Modal Set Theory MST, Zeitschr. f. Mathematikal Logik u. Grundlagen d. Mathematik, Bd.34(2), (1988), pp.123-134.
• A Note of Proofs of Falsehood , Archiv f. Mathematikal Logik u. Grundlagen 26 (3-4), (1987), pp. 169-179.
• On the Number of Steps in Proofs , Annals of Pure and Applied Logic 41(2), (1989), pp. 153-178.
• with P. Pudlak: The Number of Proof Lines and the Size of Proofs in First Order Logic, Archive for Mathematical Logic 27, (1988), pp. 69-84.
• with P. Pudlák: Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations, J. Symbolic Logic, 54(3), 1063-1079, (1989).
• with P. Pudlak: Quantified Propositional Calculi and Fragments of Bounded Arithmetic, Zeitschr. f. Mathematikal Logik u. Grundlagen d. Mathematik, Bd. 36(1), (1990), pp. 29-46.
• A Theorem on Uniform Provability of Schemes , Proc. 6th Easter Conf. on Model Theory, Wendisch-Rietz 1988, in: Seminarberichte Nr. 98, Humboldt Univ., Berlin, (1988), pp. 85-92.
• with P. Pudlak: On the Structure of Initial Segments of Models of Arithmetic, Archive for Mathematical Logic, 28(2), (1989), pp, 91-98.
• $\Pi_1$-Conservativeness in Systems of Bounded Arithmetic , unpublished typescript.
• Speed-up for Propositional Frege Systems via Generalizations of Proofs, Commentationes Mathematicae Universitas Carolinae, 30(1), (1989), pp.137-140.
• Exponentiation and Second Order Bounded Arithmetic, Annals of Pure and Applied Logic, 48(3), (1990), pp. 261-276
• with P.Pudlak and G. Takeuti: Bounded Arithmetic and the Polynomial Hierarchy, Annals of Pure and Applied Logic 52, 143-153, (1991).
• with G. Takeuti: On Bounded $\sum^1_1$-Polynomial Induction, in: Feasible Mathematics, eds. S.R. Buss and P.J.Scott, (1990), Birkhauser, pp. 259-280.
• with P. Pudlak: Propositional Provability and Models of Weak Arithmetic , in: Computer Science Logic (Kaiserlautern, Oct.'89), E. Borger, H. Kleine Buning, M.M. Richter (eds.), LNCS 440, (1990), Springer-Verlag, pp. 193-210.
• with G. Takeuti: On Induction-Free Provability, Annals of Mathematics and Artificial Intelligence, 6, (1992), pp.107-126.
• No Counter-Example Interpretation and Interactive Computation, in: Logic from Computer Science, ed. Y.N.Moschovakis, Mathematical Sciences Research Institute Publ. 21, Berkeley, Springer-Verlag, (1992), pp.287-293.
• with P. Pudlak and J. Sgall, Interactive Computations of Optimal Solutions, in: B. Rovan (ed.): Mathematical Foundations of Computer Science (B. Bystrica, August '90), LN in Computer Science 452, Springer-Verlag, (1990), pp. 48-60.
• Fragments of Bounded Arithmetic and Bounded Query Classes, Transactions of the AMS, 338(2), pp.587-598, (1993).
• with S. Buss: An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic, Proceedings of the London Mathematical Society, 69(3), pp.1-21, (1994).
• with S. Buss and G. Takeuti: Provably Total Functions in Bounded Arithmetic Theories $R^i_3, U^i_2$ and $V^i_2$, in: Arithmetic, Proof Theory and Computational Complexity , eds.P.Clote and J.Krajicek, Oxford Press, (1993), pp.116-161.
• Lower Bounds to the Size of Constant-Depth Propositional Proofs. J. of Symbolic Logic, 59(1), pp.73-86, (1994).
• with P. Pudlak and A. Woods: An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole principle. Random Structures and Algorithms, 7(1), pp.15-39,(1995).
• On Frege and Extended Frege Proof Systems , in: Feasible Mathematics II , eds. P.Clote and J.Remmel, Birkhauser, (1995), pp. 284-319.
• with P. Beame, R. Impagliazzo, T. Pitassi and P.Pudlák: Lower bounds on Hilbert.s Nullstellensatz and propositional proofs. Proceedings of the London Mathematical Society, 73(3), pp.1-26, (1996).
• with M. Chiari : Witnessing functions in bounded arithmetic and search problems , J. of Symbolic Logic, 63(3), (1998), pp.1095-1115.
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. J. of Symbolic Logic, 62(2), pp.457-486, (1997).
• with P. Pudlák: Some consequences of cryptographical conjectures for S12 and EF. Information and Computation, 140(1), pp.82-94, (1998).
• with S.Buss, R.Impagliazzo, P.Pudlak, A.A.Razborov and J.Sgall: Proof complexity in algebraic systems and bounded depth Frege systems with modular counting, Computational Complexity, 6(3), 1996/1997, pp.256-298.
• Extensions of models of $PV$, in: Logic Colloquium'95, Eds. J.A.Makowsky and E.V.Ravve, ASL/Springer Series Lecture Notes in Logic, Vol.11, (1998), pp.104-114.
• Discretely ordered modules as a first-order extension of the cutting planes proof system, J. Symbolic Logic, 63(4), (1998), pp.1582-1596.
• Interpolation by a game, Mathematical Logic Quarterly, 44(4), (1998), pp.450-458.
• with M.Baaz, P.Hajek and D.Svejda: Embedding logics into product logic, Studia Logica, 61, (1998), pp.35-47.
• with M.Chiari: Lifting independence results in bounded arithmetic, Archive for Mathematical Logic, 38(2), (1999), pp.123-138.
• Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus, in: Eds. I.Privara, P.Ruzicka, 22nd Inter. Symp. Mathematical Foundations of Computer Science(Bratislava, August '97), LN in Computer Science 1295, Springer-Verlag, (1997), pp.85-90.
• On the degree of ideal membership proofs from uniform families of polynomials over a finite field , Illinois J. of Mathematics, 45(1), (2001), pp.41-73.
• Uniform families of polynomial equations over a finite field and structures admitting an Euler characteristic of definable sets, Proc. London Mathematical Society, 3 (81), 257-284, (2000).
• On the weak pigeonhole principle, Fundamenta Mathematicae, Vol.170(1-3), (2001), pp.123-140.
• with T. Scanlon: Combinatorics with definable sets: Euler characteristics and Grothendieck rings, Bulletin of Symbolic Logic, 3(3), pp.311-330, (2000).
• On the weak pigeonhole principle, Fundamenta Mathematicae, 170(1-3), pp.123-140, (2001).
• Tautologies from pseudo-random generators, Bulletin of Symbolic Logic, 7(2), (2001), pp.197-212.
• with R.Impagliazzo: A note on conservativity relations among bounded arithmetic theories, Mathematical Logic Quaterly, 48(3), (2002), pp.375-7.
• Combinatorics of first order structures and propositional proof systems, Archive for Mathematical Logic, 43(4), (2004), pp.427-441.
• Interpolation and approximate semantic derivations, Mathematical Logic Quaterly, Vol.48(4), (2002), pp.602-606.
• Aproximate Euler characteristic, dimension, and weak pigeonhole principles, J. of Symbolic Logic, 69(1), pp.201-214, (2004).
• Dehn function and length of proofs , International Journal of Algebra and Computation, 13(5), pp.527-542, (2003).
• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds, J. of Symbolic Logic, 69(1), pp.265-286, (2004).
• Implicit proofs , J. of Symbolic Logic, 69(2), (2004), pp.387-397.
• Diagonalization in proof complexity, Fundamenta Mathematicae, 182, pp.181-192, (2004).
• Structured pigeonhole principle, search problems and hard tautologies , J. of Symbolic Logic, 70(2), (2005), pp.619-630.
• Substitutions into propositional tautologies, Information Processing Letters, 101, (2007), pp.163-167.
• with A.Skelley and N.Thapen: NP search problems in low fragments of bounded arithmetic, J. of Symbolic Logic, 72(2), pp.649-672, (2007).
• with S.Cook, Consequences of the Provability of NP \subseteq P/poly, J. of Symbolic Logic, 72(4), pp.1353-1371, (2007).
• An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams, J. of Symbolic Logic, 73(1), pp.227-237, (2008).
• A proof complexity generator, in: Logic, Methodology and Philosophy of Science: Proc. of the 13th International Congress, Eds. Clark Glymour, Wei Wang, and Dag Westerstahl, College Publications, London, (2009), pp.185-190.
• A form of feasible interpolation for constant depth Frege systems , J. of Symbolic Logic, 75(2), pp.774-784, (2010).
• A note on propositional proof complexity of some Ramsey-type statements, Archive for Mathematical Logic, 50(1-2), (2011), pp.245-255. DOI: 10.1007/s00153-010-0212-9.
• On the proof complexity of the Nisan-Wigderson generator based on a hard NP \cap coNP function, J. of Mathematical Logic, Vol.11 (1), pp.11-27, (2011). DOI: 10.1142/S0219061311000979
• A note on SAT algorithms and proof complexity, Information Processing Letters, 112 (2012), pp.490-493. DOI: 10.1016/j.ipl.2012.03.009.
• Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator, Logical methods in Computer Science, Vol. 8 (3:09) 2012, pp.1-8. DOI: 10.2168/LMCS-8(3:9)2012. ArXiv:1207.0393.
• A saturation property of structures obtained by forcing with a compact family of random variables, Archive for Mathematical Logic, 52(1), (2013), pp.19-28. DOI: 10.1007/s00153-012-0304-9. ArXiv:1207.1548.
• On the computational complexity of finding hard tautologies, Bulletin of the London Mathematical Society, 46(1), (2014), pp.111-125. DOI: 10.1112/blms/bdt071. ArXiv: 1212.1789.
• A reduction of proof complexity to computational complexity for $AC^0p$ Frege systems, Proceedings of the AMS, 143(11), (2015), pp.4951-4965. DOI: 10.1090/S0002-9939-2015-12610-X. ArXiv: 1311.2501.
• Consistency of circuit evaluation, extended resolution and total NP search problems, Forum of Mathematics, Sigma / Volume 4 / 2016, e15: DOI: 10.1017/fms.2016.13. ArXiv: 1509.03048.
• with Igor C. Oliveira, Unprovability of circuit upper bounds in Cook's theory PV, Logical methods in Computer Science, Volume 13, Issue 1, (2017). DOI : 10.23638/LMCS-13(1:4)2017. ArXiv: 1605.00263.
• A feasible interpolation for random resolution, Logical Methods in Computer Science, Volume 13, Issue 1, (2017). DOI : 10.23638/LMCS-13(1:5)2017. ArXiv: 1604.06560.
• Randomized feasible interpolation and monotone circuits with a local oracle, J. of Mathematical Logic, to appear, ArXiv: 1611.08680.
• with Igor C.Oliveira, On monotone circuits with local oracles and clique lower bounds, Chicago Journal of Theoretical Computer Science, vol.2018, nb.1, (March 2018), pp.1-18. DOI: 10.4086/cjtcs.2018.001, ArXiv: 1704.06241.

Expository papers:
• Modal Set Theory, Proc. 2nd Easter Conference on Model Theory, Wittenberg 1984, in: Seminarberichte Nr.60, Humboldt Univ., Berlin, (1984), pp.87-99.
• Generalizations of Proofs , Proc. 5th Easter Conf. on Model Theory, Wendisch-Rietz 1987, in: Seminarberichte Nr. 93, Humboldt University, Berlin, (1987), pp. 82-99.
• with P. Clote: Open Problems , in:Arithmetic, Proof Theory and Computational Complexity , eds. P.Clote and J.Krajicek, Oxford Press, (1993), pp.1-19.
• A fundamental problem of mathematical logic, Annals of the Kurt Godel Society, Springer-Verlag, Collegium Logicum, Vol.2, (1996), pp.56-64.
• On methods for proving lower bounds in propositional logic , in: Logic and Scientific Methods Eds. M. L. Dalla Chiara et al., (Vol. 1 of Proc. of the Tenth International Congress of Logic, Methodology and Philosophy of Science, Florence (August 19-25, 1995)), Synthese Library, Vol.259, Kluwer Academic Publ., Dordrecht, (1997), pp.69-83.
• Boolean circuits , in: Encyclopaedia of Mathematics, ed.M.~Hazelwinkel, Kluwer Academic Publ., (2000), pp.79-80.
• Hardness assumptions in the foundations of theoretical computer science, Archive for Mathematical Logic, 44(6), (2005), pp.667-675.
• Proof complexity, in: Laptev, A. (ed.), European congress of mathematics (ECM), Stockholm, Sweden, June 27--July 2, 2004. Zurich: European Mathematical Society, (2005), pp.221-231.
• From feasible proofs to feasible computations, in: Computer Science Logic 2010, A. Dawar and H. Veith (Eds.), LNCS 6247, Springer, Heidelberg (2010), pp.22-31.
• Expansions of pseudofinite structures and circuit and proof complexity, in: Liber Amicorum Alberti, eds.Jan van Eijck, Rosalie Iemhoff and Joost J. Joosten, Tributes Ser. Vol.30, College Publications, London, (2016), pp.195-203. ArXiv: 1505.00118.

Abstracts and extended abstracts
• Some Theorems on the Lattice of Local Interpretability Types (abstract), Commentationes Mathematicae Universitas Carolinae, 24(2), (1983), p. 387.
• A Possible Modal Reformulation of Comprehension Scheme (abstract), Commentationes Mathematicae Universitas Carolinae, 24(2), (1983), pp. 387-388.
• Measures of Complexity of Proofs (extended abstract), Abstracts of 8th Inter. Congress on Logic, Methodology and Philosophy of Science '87, Moscow, August 1987, Vol. 5, Part 1, pp. 151-154.
• Three Theorems on Bounded Arithmetic (abstract), Annual 1989 Meeting of ASL at Los Angeles, J. Symbolic Logic, 55(1), pp.377-378.
• with P. Beame, R. Impagliazzo, T. Pitassi, P.Pudlak and A. Woods: Exponential Lower Bound for the Pigeonhole Principle, in: Proc. ACM Symp. on Theory of Computing, ACM Press, (1992), pp.200-220.
• with P. Beame, R. Impagliazzo, T. Pitassi and P.Pudlak: Lower bounds on Hilbert's Nullstellensatz and propositional proofs, in: Proc. IEEE 35th Annual Symp. onFoundation of Computer Science, (1994), pp.794-806.
• Valuations of Boolean formulae in partial algebras, in: Volume of Abstracts of the Tenth International Congress Logic, Methodology and Philosophy of Science}, International Union of History and Philosophy of Science, Florence (August 19-25, 1995), (1995), pp.6-7.
• Propositional proofs, proofs of membership in polynomial ideals, and their complexity, Bulletin of the ASL, 3(1), (1997), pp.77-78.
• Bounded arithmetic, propositional logic, and complexity theory, in: Proc. of the bi-annual meeting of the Japanese Mathematical Society, Tokyo, September 1997.
• Forcing with random variables and proof complexity, eds. A.Beckmann, U.Berger, B.Löwe, and J.V.Tucker: Logical Approaches to Computational Barriers, 2nd Conference on Computability in Europe, CiE 2006, Swansea, UK, July 2006, Lecture Notes in Computer Science, Springer, (2006), pp.277-278.