Jan Krajícek

Publication Activity (10 Years)

Years Active: 1985-2024
Publications (10 Years): 27

Top Topics

Bilinear Interpolation

Complete Axiomatization

Top Venues

Electron. Colloquium Comput. Complex.

Log. Methods Comput. Sci.

Bull. Symb. Log.

Publications

Jan Krajícek
On the existence of Strong Proof Complexity Generators. Bull. Symb. Log. 30 (1) (2024)
Jan Krajícek
Extended Nullstellensatz proof systems. Electron. Colloquium Comput. Complex. (2023)
Jan Krajícek
Extended Nullstellensatz proof systems. CoRR (2023)
Jan Krajícek
A proof complexity conjecture and the Incompleteness theorem. CoRR (2023)
Jan Krajícek
A proof complexity conjecture and the Incompleteness theorem. Electron. Colloquium Comput. Complex. (2023)
Jan Krajícek
On the existence of strong proof complexity generators. CoRR (2022)
Jan Krajícek
Information in Propositional Proofs and Algorithmic Proof Search. J. Symb. Log. 87 (2) (2022)
Jan Krajícek
On the existence of strong proof complexity generators. Electron. Colloquium Comput. Complex. (2022)
Jan Krajícek
Small Circuits and Dual Weak PHP in the Universal Theory of p-time Algorithms. ACM Trans. Comput. Log. 22 (2) (2021)
Jan Krajícek
Information in propositional proofs and algorithmic proof search. Electron. Colloquium Comput. Complex. 28 (2021)
Jan Krajícek
Information in propositional proofs and algorithmic proof search. CoRR (2021)
Jan Krajícek
Small circuits and dual weak PHP in the universal theory of p-time algorithms. CoRR (2020)
Jan Krajícek
A limitation on the KPT interpolation. CoRR (2020)
Jan Bydzovsky, Jan Krajícek, Igor Carboni Oliveira
Consistency of circuit lower bounds with bounded theories. Log. Methods Comput. Sci. 16 (2) (2020)
Jan Krajícek
A limitation on the KPT interpolation. Log. Methods Comput. Sci. 16 (3) (2020)
Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajícek
Consistency of circuit lower bounds with bounded theories. Electron. Colloquium Comput. Complex. 26 (2019)
Jan Bydzovsky, Jan Krajícek, Igor Carboni Oliveira
Consistency of circuit lower bounds with bounded theories. CoRR (2019)
Jan Krajícek
The Cook-Reckhow definition. CoRR (2019)
Jan Krajícek, Igor Carboni Oliveira
On monotone circuits with local oracles and clique lower bounds. Chic. J. Theor. Comput. Sci. 2018 (2018)
Jan Krajícek
Randomized feasible interpolation and monotone circuits with a local oracle. J. Math. Log. 18 (2) (2018)
Jan Krajícek, Igor Carboni Oliveira
On monotone circuits with local oracles and clique lower bounds. CoRR (2017)
Jan Krajícek, Igor Carboni Oliveira
Unprovability of circuit upper bounds in Cook's theory PV. Log. Methods Comput. Sci. 13 (1) (2017)
Jan Krajícek
A feasible interpolation for random resolution. Log. Methods Comput. Sci. 13 (1) (2017)
Jan Krajícek, Igor Carboni Oliveira
Unprovability of circuit upper bounds in Cook's theory PV. Electron. Colloquium Comput. Complex. 23 (2016)
Jan Krajícek
Randomized feasible interpolation and monotone circuits with a local oracle. CoRR (2016)
Jan Krajícek
Expansions of pseudofinite structures and circuit and proof complexity. CoRR (2015)
Jan Krajícek
Consistency of circuit evaluation, extended resolution and total NP search problems. CoRR (2015)
Olaf Beyersdorff, Edward A. Hirsch, Jan Krajícek, Rahul Santhanam
Optimal algorithms and proofs (Dagstuhl Seminar 14421). Dagstuhl Reports 4 (10) (2014)
Jan Krajícek
A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems. CoRR (2013)
Jan Krajícek
[p] Frege systems. Electron. Colloquium Comput. Complex. 20 (2013)
Jan Krajícek
A saturation property of structures obtained by forcing with a compact family of random variables. Arch. Math. Log. 52 (1-2) (2013)
Jan Krajícek
On the computational complexity of finding hard tautologies CoRR (2012)
Jan Krajícek
Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator Log. Methods Comput. Sci. 8 (3) (2012)
Jan Krajícek
A note on SAT algorithms and proof complexity. Inf. Process. Lett. 112 (12) (2012)
Jan Krajícek
A note on propositional proof complexity of some Ramsey-type statements. Arch. Math. Log. 50 (1-2) (2011)
Jan Krajícek
On the Proof Complexity of the Nisan-Wigderson Generator based on a Hard NP ∩ coNP function. J. Math. Log. 11 (1) (2011)
Jan Krajícek
On the proof complexity of the Nisan-Wigderson generator based on a hard NP cap coNP function. Electron. Colloquium Comput. Complex. 17 (2010)
Jan Krajícek
From Feasible Proofs to Feasible Computations. CSL (2010)
Jan Krajícek
A form of feasible interpolation for constant depth Frege systems. J. Symb. Log. 75 (2) (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) (2008)
Stephen A. Cook, Jan Krajícek
. J. Symb. Log. 72 (4) (2007)
Jan Krajícek
Substitutions into propositional tautologies. Inf. Process. Lett. 101 (4) (2007)
Jan Krajícek
An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams. Electron. Colloquium Comput. Complex. 14 (007) (2007)
Jan Krajícek, Alan Skelley, Neil Thapen
NP search problems in low fragments of bounded arithmetic. J. Symb. Log. 72 (2) (2007)
Jan Krajícek
Forcing with Random Variables and Proof Complexity. CiE (2006)
Jan Krajícek
Proof Complexity Generators. ACiD (2006)
Jan Krajícek
Structured pigeonhole principle, search problems and hard tautologies. J. Symb. Log. 70 (2) (2005)
Jan Krajícek
Hardness assumptions in the foundations of theoretical computer science. Arch. Math. Log. 44 (6) (2005)
Jan Krajícek
Diagonalization in proof complexity Electron. Colloquium Comput. Complex. (018) (2004)
Jan Krajícek
Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds. J. Symb. Log. 69 (1) (2004)
Jan Krajícek
Approximate Euler characteristic, dimension, and weak pigeonhole principles. J. Symb. Log. 69 (1) (2004)
Jan Krajícek
Combinatorics of first order structures and propositional proof systems. Arch. Math. Log. 43 (4) (2004)
Jan Krajícek
Implicit proofs. J. Symb. Log. 69 (2) (2004)
Jan Krajícek
Dehn Function and Length of Proofs. Int. J. Algebra Comput. 13 (5) (2003)
Jan Krajícek
Implicit proofs Electron. Colloquium Comput. Complex. (055) (2003)
Jan Krajícek
Interpolation and Approximate Semantic Derivations. Math. Log. Q. 48 (4) (2002)
Russell Impagliazzo, Jan Krajícek
A Note on Conservativity Relations among Bounded Arithmetic Theories. Math. Log. Q. 48 (3) (2002)
Jan Krajícek
Tautologies from pseudo-random generators. Bull. Symb. Log. 7 (2) (2001)
Jan Krajícek
Tautologies from pseudo-random generators Electron. Colloquium Comput. Complex. 7 (33) (2000)
Jan Krajícek, Thomas Scanlon
Combinatorics with definable sets: Euler characteristics and Grothendieck rings. Bull. Symb. Log. 6 (3) (2000)
Mario Chiari, Jan Krajícek
Lifting independence results in bounded arithmetic. Arch. Math. Log. 38 (2) (1999)
Jan Krajícek
Interpolation by a Game. Math. Log. Q. 44 (1998)
Mario Chiari, Jan Krajícek
Witnessing Functions in Bounded Arithmetic and Search Problems. J. Symb. Log. 63 (3) (1998)
Jan Krajícek
Discretely Ordered Modules as a First-Order Extension of The Cutting Planes Proof System. J. Symb. Log. 63 (4) (1998)
Jan Krajícek, Pavel Pudlák
and EF. Inf. Comput. 140 (1) (1998)
Matthias Baaz, Petr Hájek, David Svejda, Jan Krajícek
Embedding Logics into Product Logic. Stud Logica 61 (1) (1998)
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)
Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jirí Sgall
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Comput. Complex. 6 (3) (1997)
Jan Krajícek
Interpolation by a Game Electron. Colloquium Comput. Complex. 4 (15) (1997)
Jan Krajícek
Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic. J. Symb. Log. 62 (2) (1997)
Jan Krajícek
Extensions of Models of PV. Logic Colloquium (1995)
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) (1995)
Jan Krajícek
Lower Bounds to the Size of Constant-Depth Propositional Proofs. J. Symb. Log. 59 (1) (1994)
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 Electron. Colloquium Comput. Complex. 1 (18) (1994)
Jan Krajícek, Pavel Pudlák
Some Consequences of Cryptographical Conjectures for S_2^1 and EF. LCC (1994)
Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák
Lower Bound on Hilbert's Nullstellensatz and propositional proofs FOCS (1994)
Jan Krajícek, Gaisi Takeuti
On Induction-Free Provability. Ann. Math. Artif. Intell. 6 (1-3) (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)
Jan Krajícek, Pavel Pudlák, Gaisi Takeuti
Bounded Arithmetic and the Polynomial Hierarchy. Ann. Pure Appl. Log. 52 (1-2) (1991)
Jan Krajícek
Exponentiation and Second-Order Bounded Arithmetic. Ann. Pure Appl. Log. 48 (3) (1990)
Jan Krajícek, Pavel Pudlák, Jirí Sgall
Interactive Computations of Optimal Solutions. MFCS (1990)
Jan Krajícek, Pavel Pudlák
Quantified propositional calculi and fragments of bounded arithmetic. Math. Log. Q. 36 (1) (1990)
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) (1989)
Jan Krajícek
On the Number of Steps in Proofs. Ann. Pure Appl. Log. 41 (2) (1989)
Jan Krajícek, Pavel Pudlák
Propositional Provability and Models of Weak Arithmetic. CSL (1989)
Jan Krajícek, Pavel Pudlák
On the structure of initial segments of models of arithmetic. Arch. Math. Log. 28 (2) (1989)
Jan Krajícek, Pavel Pudlák
The number of proof lines and the size of proofs in first order logic. Arch. Math. Log. 27 (1) (1988)
Jan Krajícek
Some Results and Problems in The Modal Set Theory MST. Math. Log. Q. 34 (2) (1988)
Jan Krajícek
A note on proofs of falsehood. Arch. Math. Log. 26 (1) (1987)
Jan Krajícek
A Possible Modal Formulation of Comprehension Scheme. Math. Log. Q. 33 (5) (1987)
Jan Krajícek
Some Theorems on the Lattice of Local Interpretability Types. Math. Log. Q. 31 (29-30) (1985)