Jan Krajicek' bibliography

Research papers (and the most recent),
expository papers (and the most recent ),
old lecture notes,
books and
edited volumes.


  • The published papers may differ from versions available here by changes done in the page proofs.

  • Chapters in books are listed among papers - both research and expository.

  • Starting with 2012 I send all preprints to the ArXiv archive.

  • My ORCID id.

  • As a matter of principle I do not co-sign papers resulting from thesis work of my (PhD or MSc) students.


    I request that those colleagues who leave some of their papers behind pay-walls (and do not keep freely available even preliminary versions) do contribute for each download here 10 EUR to a good cause.


    Thesis and habilitations

    • RNDr.Thesis: "Non-classical Foundations of Mathematics", in Czech, Charles University, April 1985.

    • CSc.Habilitation: "Complexity of Formal Proofs", a collection of five papers (in English) with an introduction and overview (in Czech), Academy of Sciences, September 1989.

    • DrSc.Habilitation: "Bounded Arithmetic, Propositional Calculus, and Complexity Theory", a collection of ten papers (in English) with an introduction and overview (in Czech), Academy of Sciences, August 1992.

    • Doc.Habilitation: "Lower bounds in propositional calculus and independence results in bounded arithmetic", a collection of twelve papers (in English) with an introduction and overview (in Czech), Charles University, May 2000.

    Abstracts and extended abstracts - selected

    • "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 $8^{\mbox{th}}$ 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.Pudl\'{a}k and A. Woods: "Exponential Lower Bound for the Pigeonhole Principle" (extended abstract), in: Proc. ACM Symp. on Theory of Computing, ACM Press, (1992), pp.200-220.

    • "Problems of complexity theory in models of bounded arithmetic" (extended abstract), in: {\em Proof Theory, Complexity and Metamathematics}, Technological University of Vienna and Kurt Godel Society, (1994).

    • "A non-conservation result for bounded arithmetic and search problems" (abstract), in: {\em Proof Theory, Complexity and Metamathematics}, Technological University of Vienna and Kurt Godel Society, (1994).

    • with P. Beame, R. Impagliazzo, T. Pitassi and P.Pudl\'{a}k: "Lower bounds on Hilbert's Nullstellensatz and propositional proofs" (extended abstract), in: Proc. IEEE 35$^{\mbox{th}}$ Annual Symp. on Foundation of Computer Science, (1994), pp.794-806.

    • "Valuations of Boolean formulae in partial algebras", in: Volume of Abstracts of the Tenth International Congress {\em 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", in: Abstracts of the annual European meeting of the Association of Symbolic Logic, {\em Logic Colloquium 95}, Haifa (August 9-17, 1995), (1995), p.PROOF-22. Also in: {\em Bulletin of the ASL}, {\bf 3(1)}, (1997), pp.77-78.

    • "Classical propositional logic and its complexity", a syllabus and references for an advanced logic course given at the {\em Eight European Summer School in Logic, Language and Information} held in Prague, August 12-23, 1996.
      Available online.

    • ``Bounded arithmetic, propositional logic, and complexity theory'', in: Proc. of the bi-annual meeting of the Japanese Mathematical Society, Tokyo, September 1997.

    • ``Effective interpolation'', a syllabus and references for a course given at the Tohoku University in Sendai (Japan), October 2-4, 1997.
      Available online.

    • "Forcing with random variables and proof complexity", eds. A.Beckmann, U.Berger, B.Lwe, 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. Pdf file.

    • Proof search problem (ext.abstract)
      in: Mathematical Logic: Proof Theory, Constructive Mathematics (9.-13.11.2020),
      Oberwolfach Reports (OWR), Report No. 34/2020, (2020), pp.45-46.
      DOI, slides.

    Expository papers


    Research papers



    Lecture notes (old)




    Books




    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. 424 pp., (2004).

    • with M. Baaz and S. Friedman, "Logic Colloquium'01",
      Proceedings of the European ASL meeting in Vienna 2001,
      LN in Logic, Vol.20, Assoc. for Symb. Logic, A K Peters, Ltd., and Wellesley (Mass.US), 486 pp., (2005).