Jan Krajícek

Jan Krajícek: A saturation property of structures obtained by forcing with a compact family of random variables. Arch. Math. Log. 52(1-2): 19-28 (2013)

Jan Krajícek: Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator. Logical Methods in Computer Science 8(3) (2012)

Jan Krajícek: A note on SAT algorithms and proof complexity. Inf. Process. Lett. 112(12): 490-493 (2012)

Jan Krajícek: On the computational complexity of finding hard tautologies. CoRR abs/1212.1789 (2012)

Jan Krajícek: A note on propositional proof complexity of some Ramsey-type statements. Arch. Math. Log. 50(1-2): 245-255 (2011)

Jan Krajícek: A form of feasible interpolation for constant depth Frege systems. J. Symb. Log. 75(2): 774-784 (2010)

Jan Krajícek: From Feasible Proofs to Feasible Computations. CSL 2010: 22-31

Jan Krajícek: On the proof complexity of the Nisan-Wigderson generator based on a hard NP cap coNP function. Electronic Colloquium on Computational Complexity (ECCC) 17: 54 (2010)

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

Jan Krajícek: Substitutions into propositional tautologies. Inf. Process. Lett. 101(4): 163-167 (2007)

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

Stephen A. Cook, Jan Krajícek: Consequences of the provability of NP SUBSET OF OR EQUAL TO P/poly. J. Symb. Log. 72(4): 1353-1371 (2007)

Jan Krajícek: An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams. Electronic Colloquium on Computational Complexity (ECCC) 14(007) (2007)

Jan Krajícek: Proof Complexity Generators. ACiD 2006: 3

Jan Krajícek: Forcing with Random Variables and Proof Complexity. CiE 2006: 277-278

Jan Krajícek: Hardness assumptions in the foundations of theoretical computer science. Arch. Math. Log. 44(6): 667-675 (2005)

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

Jan Krajícek: Combinatorics of first order structures and propositional proof systems. Arch. Math. Log. 43(4): 427-441 (2004)

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

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

Jan Krajícek: Implicit proofs. J. Symb. Log. 69(2): 387-397 (2004)

Jan Krajícek: Diagonalization in proof complexity. Electronic Colloquium on Computational Complexity (ECCC)(018) (2004)

Jan Krajícek: Dehn Function and Length of Proofs. IJAC 13(5): 527-541 (2003)

Jan Krajícek: Implicit proofs. Electronic Colloquium on Computational Complexity (ECCC)(055) (2003)

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

Jan Krajícek: Interpolation and Approximate Semantic Derivations. Math. Log. Q. 48(4): 602-606 (2002)

Jan Krajícek: Tautologies from pseudo-random generators. Bulletin of Symbolic Logic 7(2): 197-212 (2001)

Jan Krajícek, Thomas Scanlon: Combinatorics with definable sets: Euler characteristics and Grothendieck rings. Bulletin of Symbolic Logic 3(3): 311-330 (2000)

Jan Krajícek: Tautologies from pseudo-random generators. Electronic Colloquium on Computational Complexity (ECCC) 7(33) (2000)

Mario Chiari, Jan Krajícek: Lifting independence results in bounded arithmetic. Arch. Math. Log. 38(2): 123-138 (1999)

Jan Krajícek, Pavel Pudlák: Some Consequences of Cryptographical Conjectures for S¹₂ and EF. Inf. Comput. 140(1): 82-94 (1998)

Mario Chiari, Jan Krajícek: Witnessing Functions in Bounded Arithmetic and Search Problems. J. Symb. Log. 63(3): 1095-1115 (1998)

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

Jan Krajícek: Interpolation by a Game. Math. Log. Q. 44: 450-458 (1998)

Matthias Baaz, Petr Hájek, David Svejda, Jan Krajícek: Embedding Logics into Product Logic. Studia Logica 61(1): 35-47 (1998)

Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jiri Sgall: Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Computational Complexity 6(3): 256-298 (1997)

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

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

Jan Krajícek: Interpolation by a Game. Electronic Colloquium on Computational Complexity (ECCC) 4(15) (1997)

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

Jan Krajícek: Lower Bounds to the Size of Constant-Depth Propositional Proofs. J. Symb. Log. 59(1): 73-86 (1994)

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

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

Jan Krajícek, Pavel Pudlák, Alan R. Woods: An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle. Electronic Colloquium on Computational Complexity (ECCC) 1(18) (1994)

Jan Krajícek, Gaisi Takeuti: On Induction-Free Provability. Ann. Math. Artif. Intell. 6(1-3): 107-125 (1992)

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

Jan Krajícek, Pavel Pudlák, Gaisi Takeuti: Bounded Arithmetic and the Polynomial Hierarchy. Ann. Pure Appl. Logic 52(1-2): 143-153 (1991)

Jan Krajícek: Exponentiation and Second-Order Bounded Arithmetic. Ann. Pure Appl. Logic 48(3): 261-276 (1990)

Jan Krajícek, Pavel Pudlák, Jiri Sgall: Interactive Computations of Optimal Solutions. MFCS 1990: 48-60

Jan Krajícek: On the Number of Steps in Proofs. Ann. Pure Appl. Logic 41(2): 153-178 (1989)

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

Jan Krajícek, Pavel Pudlák: Propositional Provability and Models of Weak Arithmetic. CSL 1989: 193-210