Jan Krajícek

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