Some Theorems on the Lattice of Local Interpretability Types. - Jan Krajícek (Math. Log. Q., 1985)

A note on proofs of falsehood. - Jan Krajícek (Arch. Math. Log., 1987)

A Possible Modal Formulation of Comprehension Scheme. - Jan Krajícek (Math. Log. Q., 1987)

The number of proof lines and the size of proofs in first order logic. - Jan Krajícek; Pavel Pudlák (Arch. Math. Log., 1988)

Some Results and Problems in The Modal Set Theory MST. - Jan Krajícek (Math. Log. Q., 1988)

Propositional Provability and Models of Weak Arithmetic. - Jan Krajícek; Pavel Pudlák (CSL, 1989)

On the structure of initial segments of models of arithmetic. - Jan Krajícek; Pavel Pudlák (Arch. Math. Log., 1989)

On the Number of Steps in Proofs. - Jan Krajícek (Ann. Pure Appl. Log., 1989)

Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations. - Jan Krajícek; Pavel Pudlák (J. Symb. Log., 1989)

Interactive Computations of Optimal Solutions. - Jan Krajícek; Pavel Pudlák; Jirí Sgall (MFCS, 1990)

Exponentiation and Second-Order Bounded Arithmetic. - Jan Krajícek (Ann. Pure Appl. Log., 1990)

Quantified propositional calculi and fragments of bounded arithmetic. - Jan Krajícek; Pavel Pudlák (Math. Log. Q., 1990)

Bounded Arithmetic and the Polynomial Hierarchy. - Jan Krajícek; Pavel Pudlák; Gaisi Takeuti (Ann. Pure Appl. Log., 1991)

Exponential Lower Bounds for the Pigeonhole Principle - Paul Beame; Russell Impagliazzo; Jan Krajícek; Toniann Pitassi; Pavel Pudlák; Alan R. Woods (STOC, 1992)

On Induction-Free Provability. - Jan Krajícek; Gaisi Takeuti (Ann. Math. Artif. Intell., 1992)

Lower Bound on Hilbert's Nullstellensatz and propositional proofs - Paul Beame; Russell Impagliazzo; Jan Krajícek; Toniann Pitassi; Pavel Pudlák (FOCS, 1994)

Some Consequences of Cryptographical Conjectures for S_2^1 and EF. - Jan Krajícek; Pavel Pudlák (LCC, 1994)

An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle - Jan Krajícek; Pavel Pudlák; Alan R. Woods (Electron. Colloquium Comput. Complex., 1994)

Lower Bounds to the Size of Constant-Depth Propositional Proofs. - Jan Krajícek (J. Symb. Log., 1994)

Bounded arithmetic, propositional logic, and complexity theory. - Jan Krajícek (Cambridge University Press, 1995)

Extensions of Models of PV. - Jan Krajícek (Logic Colloquium, 1995)

An Exponenetioal Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle. - Jan Krajícek; Pavel Pudlák; Alan R. Woods (Random Struct. Algorithms, 1995)

Lower Bounds for a Proof System with an Expentential Speed-up over Constant-Depth Frege Systems and over Polynomial Calculus. - Jan Krajícek (MFCS, 1997)

Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. - Samuel R. Buss; Russell Impagliazzo; Jan Krajícek; Pavel Pudlák; Alexander A. Razborov; Jirí Sgall (Comput. Complex., 1997)

Interpolation by a Game - Jan Krajícek (Electron. Colloquium Comput. Complex., 1997)

Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic. - Jan Krajícek (J. Symb. Log., 1997)

Some Consequences of Cryptographical Conjectures for S12 and EF. - Jan Krajícek; Pavel Pudlák (Inf. Comput., 1998)

Witnessing Functions in Bounded Arithmetic and Search Problems. - Mario Chiari; Jan Krajícek (J. Symb. Log., 1998)

Discretely Ordered Modules as a First-Order Extension of The Cutting Planes Proof System. - Jan Krajícek (J. Symb. Log., 1998)

Embedding Logics into Product Logic. - Matthias Baaz; Petr Hájek 001; David Svejda; Jan Krajícek (Stud Logica, 1998)

Lifting independence results in bounded arithmetic. - Mario Chiari; Jan Krajícek (Arch. Math. Log., 1999)

Combinatorics with definable sets: Euler characteristics and Grothendieck rings. - Jan Krajícek; Thomas Scanlon (Bull. Symb. Log., 2000)

Tautologies from pseudo-random generators. - Jan Krajícek (Bull. Symb. Log., 2001)

A Note on Conservativity Relations among Bounded Arithmetic Theories. - Russell Impagliazzo; Jan Krajícek (Math. Log. Q., 2002)

Interpolation and Approximate Semantic Derivations. - Jan Krajícek (Math. Log. Q., 2002)

Dehn Function and Length of Proofs. - Jan Krajícek (Int. J. Algebra Comput., 2003)

Combinatorics of first order structures and propositional proof systems. - Jan Krajícek (Arch. Math. Log., 2004)

Diagonalization in proof complexity - Jan Krajícek (Electron. Colloquium Comput. Complex., 2004)

Approximate Euler characteristic, dimension, and weak pigeonhole principles. - Jan Krajícek (J. Symb. Log., 2004)

Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds. - Jan Krajícek (J. Symb. Log., 2004)

Implicit proofs. - Jan Krajícek (J. Symb. Log., 2004)

Hardness assumptions in the foundations of theoretical computer science. - Jan Krajícek (Arch. Math. Log., 2005)

Structured pigeonhole principle, search problems and hard tautologies. - Jan Krajícek (J. Symb. Log., 2005)

Proof Complexity Generators. - Jan Krajícek (ACiD, 2006)

Forcing with Random Variables and Proof Complexity. - Jan Krajícek (CiE, 2006)

Substitutions into propositional tautologies. - Jan Krajícek (Inf. Process. Lett., 2007)

Consequences of the provability of NP ⊆ P/poly. - Stephen A. Cook; Jan Krajícek (J. Symb. Log., 2007)

NP search problems in low fragments of bounded arithmetic. - Jan Krajícek; Alan Skelley; Neil Thapen (J. Symb. Log., 2007)

An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams. - Jan Krajícek (J. Symb. Log., 2008)

From Feasible Proofs to Feasible Computations. - Jan Krajícek (CSL, 2010)

On the proof complexity of the Nisan-Wigderson generator based on a hard NP cap coNP function. - Jan Krajícek (Electron. Colloquium Comput. Complex., 2010)

A form of feasible interpolation for constant depth Frege systems. - Jan Krajícek (J. Symb. Log., 2010)

Forcing with Random Variables and Proof Complexity. - Jan Krajícek (Cambridge University Press, 2011)

A note on propositional proof complexity of some Ramsey-type statements. - Jan Krajícek (Arch. Math. Log., 2011)

On the Proof Complexity of the Nisan-Wigderson Generator based on a Hard NP ∩ coNP function. - Jan Krajícek (J. Math. Log., 2011)

Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator - Jan Krajícek (Log. Methods Comput. Sci., 2012)

On the computational complexity of finding hard tautologies - Jan Krajícek (CoRR, 2012)

A note on SAT algorithms and proof complexity. - Jan Krajícek (Inf. Process. Lett., 2012)

A saturation property of structures obtained by forcing with a compact family of random variables. - Jan Krajícek (Arch. Math. Log., 2013)

A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems. - Jan Krajícek (CoRR, 2013)

A reduction of proof complexity to computational complexity for AC0[p] Frege systems. - Jan Krajícek (Electron. Colloquium Comput. Complex., 2013)

Optimal algorithms and proofs (Dagstuhl Seminar 14421). - Olaf Beyersdorff; Edward A. Hirsch; Jan Krajícek; Rahul Santhanam (Dagstuhl Reports, 2014)

Expansions of pseudofinite structures and circuit and proof complexity. - Jan Krajícek (CoRR, 2015)

Consistency of circuit evaluation, extended resolution and total NP search problems. - Jan Krajícek (CoRR, 2015)

Unprovability of circuit upper bounds in Cook's theory PV. - Jan Krajícek; Igor Carboni Oliveira (Electron. Colloquium Comput. Complex., 2016)

A feasible interpolation for random resolution. - Jan Krajícek (Log. Methods Comput. Sci., 2017)

On monotone circuits with local oracles and clique lower bounds. - Jan Krajícek; Igor C. Oliveira 001 (Chic. J. Theor. Comput. Sci., 2018)

Randomized feasible interpolation and monotone circuits with a local oracle. - Jan Krajícek (J. Math. Log., 2018)

The Cook-Reckhow definition. - Jan Krajícek (CoRR, 2019)

Consistency of circuit lower bounds with bounded theories. - Jan Bydzovsky; Igor Carboni Oliveira; Jan Krajícek (Electron. Colloquium Comput. Complex., 2019)

A limitation on the KPT interpolation. - Jan Krajícek (Log. Methods Comput. Sci., 2020)

Small Circuits and Dual Weak PHP in the Universal Theory of p-time Algorithms. - Jan Krajícek (ACM Trans. Comput. Log., 2021)

Information in Propositional Proofs and Algorithmic Proof Search. - Jan Krajícek (J. Symb. Log., 2022)

The Cook-Reckhow Definition. - Jan Krajícek (Logic, Automata, and Computational Complexity, 2023)

Extended Nullstellensatz proof systems. - Jan Krajícek (Electron. Colloquium Comput. Complex., 2023)

A proof complexity conjecture and the Incompleteness theorem. - Jan Krajícek (Electron. Colloquium Comput. Complex., 2023)

On the existence of Strong Proof Complexity Generators. - Jan Krajícek (Bull. Symb. Log., 2024)

On NP ∩ coNP proof complexity generators. - Jan Krajícek (CoRR, 2025)