Jan Krajícek

According to our database, Jan Krajícek authored at least 77 papers between 1985 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

On the existence of Strong Proof Complexity Generators.

Jan Krajícek

Bull. Symb. Log., 2024

2023

A proof complexity conjecture and the Incompleteness theorem.

Jan Krajícek

Electron. Colloquium Comput. Complex., 2023

Extended Nullstellensatz proof systems.

Jan Krajícek

Electron. Colloquium Comput. Complex., 2023

The Cook-Reckhow Definition.

Jan Krajícek

Proceedings of the Logic, 2023

2022

Information in Propositional Proofs and Algorithmic Proof Search.

Jan Krajícek

J. Symb. Log., 2022

2021

Small Circuits and Dual Weak PHP in the Universal Theory of p-time Algorithms.

Jan Krajícek

ACM Trans. Comput. Log., 2021

2020

A limitation on the KPT interpolation.

Jan Krajícek

Log. Methods Comput. Sci., 2020

2019

Consistency of circuit lower bounds with bounded theories.

Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajícek

Electron. Colloquium Comput. Complex., 2019

The Cook-Reckhow definition.

Jan Krajícek

CoRR, 2019

2018

Randomized feasible interpolation and monotone circuits with a local oracle.

Jan Krajícek

J. Math. Log., 2018

On monotone circuits with local oracles and clique lower bounds.

Jan Krajícek, Igor C. Oliveira

Chic. J. Theor. Comput. Sci., 2018

2017

A feasible interpolation for random resolution.

Jan Krajícek

Log. Methods Comput. Sci., 2017

2016

Unprovability of circuit upper bounds in Cook's theory PV.

Jan Krajícek, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2016

2015

Consistency of circuit evaluation, extended resolution and total NP search problems.

Jan Krajícek

CoRR, 2015

Expansions of pseudofinite structures and circuit and proof complexity.

Jan Krajícek

CoRR, 2015

2014

Optimal algorithms and proofs (Dagstuhl Seminar 14421).

Olaf Beyersdorff, Edward A. Hirsch, Jan Krajícek, Rahul Santhanam

Dagstuhl Reports, 2014

2013

A reduction of proof complexity to computational complexity for AC⁰[p] Frege systems.

Jan Krajícek

Electron. Colloquium Comput. Complex., 2013

A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems.

Jan Krajícek

CoRR, 2013

A saturation property of structures obtained by forcing with a compact family of random variables.

Jan Krajícek

Arch. Math. Log., 2013

2012

A note on SAT algorithms and proof complexity.

Jan Krajícek

Inf. Process. Lett., 2012

On the computational complexity of finding hard tautologies

Jan Krajícek

CoRR, 2012

Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator

Jan Krajícek

Log. Methods Comput. Sci., 2012

2011

On the Proof Complexity of the Nisan-Wigderson Generator based on a Hard NP ∩ coNP function.

Jan Krajícek

J. Math. Log., 2011

A note on propositional proof complexity of some Ramsey-type statements.

Jan Krajícek

Arch. Math. Log., 2011

Forcing with Random Variables and Proof Complexity.

Jan Krajícek

London Mathematical Society lecture note series 382, Cambridge University Press, ISBN: 978-0-521-15433-8, 2011

2010

A form of feasible interpolation for constant depth Frege systems.

Jan Krajícek

J. Symb. Log., 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

From Feasible Proofs to Feasible Computations.

Jan Krajícek

Proceedings of the Computer Science Logic, 24th International Workshop, 2010

2008

An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams.

Jan Krajícek

J. Symb. Log., 2008

2007

NP search problems in low fragments of bounded arithmetic.

Jan Krajícek, Alan Skelley, Neil Thapen

J. Symb. Log., 2007

Consequences of the provability of <i>NP</i> ⊆ <i>P/poly</i>.

Stephen A. Cook, Jan Krajícek

J. Symb. Log., 2007

Substitutions into propositional tautologies.

Jan Krajícek

Inf. Process. Lett., 2007

2006

Forcing with Random Variables and Proof Complexity.

Jan Krajícek

Proceedings of the Logical Approaches to Computational Barriers, 2006

Proof Complexity Generators.

Jan Krajícek

Proceedings of the Algorithms and Complexity in Durham 2006, 2006

2005

Structured pigeonhole principle, search problems and hard tautologies.

Jan Krajícek

J. Symb. Log., 2005

Hardness assumptions in the foundations of theoretical computer science.

Jan Krajícek

Arch. Math. Log., 2005

2004

Implicit proofs.

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

Approximate Euler characteristic, dimension, and weak pigeonhole principles.

Jan Krajícek

J. Symb. Log., 2004

Diagonalization in proof complexity

Jan Krajícek

Electron. Colloquium Comput. Complex., 2004

Combinatorics of first order structures and propositional proof systems.

Jan Krajícek

Arch. Math. Log., 2004

2003

Dehn Function and Length of Proofs.

Jan Krajícek

Int. J. Algebra Comput., 2003

2002

Interpolation and Approximate Semantic Derivations.

Jan Krajícek

Math. Log. Q., 2002

A Note on Conservativity Relations among Bounded Arithmetic Theories.

Russell Impagliazzo, Jan Krajícek

Math. Log. Q., 2002

2001

Tautologies from pseudo-random generators.

Jan Krajícek

Bull. Symb. Log., 2001

2000

Combinatorics with definable sets: Euler characteristics and Grothendieck rings.

Jan Krajícek, Thomas Scanlon

Bull. Symb. Log., 2000

1999

Lifting independence results in bounded arithmetic.

Mario Chiari, Jan Krajícek

Arch. Math. Log., 1999

1998

Embedding Logics into Product Logic.

Matthias Baaz, Petr Hájek, David Svejda, Jan Krajícek

Stud Logica, 1998

Discretely Ordered Modules as a First-Order Extension of The Cutting Planes Proof System.

Jan Krajícek

J. Symb. Log., 1998

Witnessing Functions in Bounded Arithmetic and Search Problems.

Mario Chiari, Jan Krajícek

J. Symb. Log., 1998

Some Consequences of Cryptographical Conjectures for S¹₂ and EF.

Jan Krajícek, Pavel Pudlák

Inf. Comput., 1998

1997

Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic.

Jan Krajícek

J. Symb. Log., 1997

Interpolation by a Game

Jan Krajícek

Electron. Colloquium Comput. Complex., 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

Lower Bounds for a Proof System with an Expentential Speed-up over Constant-Depth Frege Systems and over Polynomial Calculus.

Jan Krajícek

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

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

Extensions of Models of PV.

Jan Krajícek

Proceedings of the Annual European Summer Meeting of the Association of Symbolic Logic, 1995

Bounded arithmetic, propositional logic, and complexity theory.

Jan Krajícek

Encyclopedia of mathematics and its applications 60, Cambridge University Press, ISBN: 978-0-521-45205-2, 1995

1994

Lower Bounds to the Size of Constant-Depth Propositional Proofs.

Jan Krajícek

J. Symb. Log., 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

Some Consequences of Cryptographical Conjectures for S_2^1 and EF.

Jan Krajícek, Pavel Pudlák

Proceedings of the Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, 1994

Lower Bound on Hilbert's Nullstellensatz and propositional proofs

Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1992

On Induction-Free Provability.

Jan Krajícek, Gaisi Takeuti

Ann. Math. Artif. Intell., 1992

Exponential Lower Bounds for the Pigeonhole Principle

Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, Alan R. Woods

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991

Bounded Arithmetic and the Polynomial Hierarchy.

Jan Krajícek, Pavel Pudlák, Gaisi Takeuti

Ann. Pure Appl. Log., 1991

1990

Quantified propositional calculi and fragments of bounded arithmetic.

Jan Krajícek, Pavel Pudlák

Math. Log. Q., 1990

Exponentiation and Second-Order Bounded Arithmetic.

Jan Krajícek

Ann. Pure Appl. Log., 1990

Interactive Computations of Optimal Solutions.

Jan Krajícek, Pavel Pudlák, Jirí Sgall

Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

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

On the Number of Steps in Proofs.

Jan Krajícek

Ann. Pure Appl. Log., 1989

On the structure of initial segments of models of arithmetic.

Jan Krajícek, Pavel Pudlák

Arch. Math. Log., 1989

Propositional Provability and Models of Weak Arithmetic.

Jan Krajícek, Pavel Pudlák

Proceedings of the CSL '89, 1989

1988

Some Results and Problems in The Modal Set Theory MST.

Jan Krajícek

Math. Log. Q., 1988

The number of proof lines and the size of proofs in first order logic.

Jan Krajícek, Pavel Pudlák

Arch. Math. Log., 1988

1987

A Possible Modal Formulation of Comprehension Scheme.

Jan Krajícek

Math. Log. Q., 1987

A note on proofs of falsehood.

Jan Krajícek

Arch. Math. Log., 1987

1985

Some Theorems on the Lattice of Local Interpretability Types.

Jan Krajícek

Math. Log. Q., 1985