Jan Krajícek

According to our database1, Jan Krajícek authored at least 71 papers between 1985 and 2018.

Collaborative distances :

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2018
On monotone circuits with local oracles and clique lower bounds.
Chicago J. Theor. Comput. Sci., 2018

2017
On monotone circuits with local oracles and clique lower bounds.
CoRR, 2017

Unprovability of circuit upper bounds in Cook's theory PV.
Logical Methods in Computer Science, 2017

A feasible interpolation for random resolution.
Logical Methods in Computer Science, 2017

2016
Unprovability of circuit upper bounds in Cook's theory PV.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Randomized feasible interpolation and monotone circuits with a local oracle.
CoRR, 2016

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

Expansions of pseudofinite structures and circuit and proof complexity.
CoRR, 2015

2014
Optimal algorithms and proofs (Dagstuhl Seminar 14421).
Dagstuhl Reports, 2014

2013
A reduction of proof complexity to computational complexity for AC0[p] Frege systems.
Electronic Colloquium on Computational Complexity (ECCC), 2013

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

A saturation property of structures obtained by forcing with a compact family of random variables.
Arch. Math. Log., 2013

2012
A note on SAT algorithms and proof complexity.
Inf. Process. Lett., 2012

On the computational complexity of finding hard tautologies
CoRR, 2012

Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator
Logical Methods in Computer Science, 2012

2011
A note on propositional proof complexity of some Ramsey-type statements.
Arch. Math. Log., 2011

Forcing with Random Variables and Proof Complexity.
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.
J. Symb. Log., 2010

On the proof complexity of the Nisan-Wigderson generator based on a hard NP cap coNP function.
Electronic Colloquium on Computational Complexity (ECCC), 2010

From Feasible Proofs to Feasible Computations.
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.
J. Symb. Log., 2008

2007
NP search problems in low fragments of bounded arithmetic.
J. Symb. Log., 2007

Consequences of the provability of NPP/poly.
J. Symb. Log., 2007

Substitutions into propositional tautologies.
Inf. Process. Lett., 2007

An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams.
Electronic Colloquium on Computational Complexity (ECCC), 2007

2006
Forcing with Random Variables and Proof Complexity.
Proceedings of the Logical Approaches to Computational Barriers, 2006

Proof Complexity Generators.
Proceedings of the Algorithms and Complexity in Durham 2006, 2006

2005
Structured pigeonhole principle, search problems and hard tautologies.
J. Symb. Log., 2005

Hardness assumptions in the foundations of theoretical computer science.
Arch. Math. Log., 2005

2004
Implicit proofs.
J. Symb. Log., 2004

Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds.
J. Symb. Log., 2004

Approximate Euler characteristic, dimension, and weak pigeonhole principles.
J. Symb. Log., 2004

Diagonalization in proof complexity
Electronic Colloquium on Computational Complexity (ECCC), 2004

Combinatorics of first order structures and propositional proof systems.
Arch. Math. Log., 2004

2003
Dehn Function and Length of Proofs.
IJAC, 2003

Implicit proofs
Electronic Colloquium on Computational Complexity (ECCC), 2003

2002
Interpolation and Approximate Semantic Derivations.
Math. Log. Q., 2002

A Note on Conservativity Relations among Bounded Arithmetic Theories.
Math. Log. Q., 2002

2001
Tautologies from pseudo-random generators.
Bulletin of Symbolic Logic, 2001

2000
Tautologies from pseudo-random generators
Electronic Colloquium on Computational Complexity (ECCC), 2000

Combinatorics with definable sets: Euler characteristics and Grothendieck rings.
Bulletin of Symbolic Logic, 2000

1999
Lifting independence results in bounded arithmetic.
Arch. Math. Log., 1999

1998
Embedding Logics into Product Logic.
Studia Logica, 1998

Interpolation by a Game.
Math. Log. Q., 1998

Discretely Ordered Modules as a First-Order Extension of The Cutting Planes Proof System.
J. Symb. Log., 1998

Witnessing Functions in Bounded Arithmetic and Search Problems.
J. Symb. Log., 1998

Some Consequences of Cryptographical Conjectures for S12 and EF.
Inf. Comput., 1998

1997
Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic.
J. Symb. Log., 1997

Interpolation by a Game
Electronic Colloquium on Computational Complexity (ECCC), 1997

Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.
Computational Complexity, 1997

Lower Bounds for a Proof System with an Expentential Speed-up over Constant-Depth Frege Systems and over Polynomial Calculus.
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.
Random Struct. Algorithms, 1995

1994
Lower Bounds to the Size of Constant-Depth Propositional Proofs.
J. Symb. Log., 1994

An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle
Electronic Colloquium on Computational Complexity (ECCC), 1994

Some Consequences of Cryptographical Conjectures for S_2^1 and EF.
Proceedings of the Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, 1994

Lower Bound on Hilbert's Nullstellensatz and propositional proofs
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1992
On Induction-Free Provability.
Ann. Math. Artif. Intell., 1992

Exponential Lower Bounds for the Pigeonhole Principle
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991
Bounded Arithmetic and the Polynomial Hierarchy.
Ann. Pure Appl. Logic, 1991

1990
Quantified propositional calculi and fragments of bounded arithmetic.
Math. Log. Q., 1990

Exponentiation and Second-Order Bounded Arithmetic.
Ann. Pure Appl. Logic, 1990

Interactive Computations of Optimal Solutions.
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.
J. Symb. Log., 1989

On the Number of Steps in Proofs.
Ann. Pure Appl. Logic, 1989

On the structure of initial segments of models of arithmetic.
Arch. Math. Log., 1989

Propositional Provability and Models of Weak Arithmetic.
Proceedings of the CSL '89, 1989

1988
Some Results and Problems in The Modal Set Theory MST.
Math. Log. Q., 1988

The number of proof lines and the size of proofs in first order logic.
Arch. Math. Log., 1988

1987
A Possible Modal Formulation of Comprehension Scheme.
Math. Log. Q., 1987

A note on proofs of falsehood.
Arch. Math. Log., 1987

1985
Some Theorems on the Lattice of Local Interpretability Types.
Math. Log. Q., 1985


  Loading...