Jan Krajicek
Jan Krajicek
Professor of Mathematical Logic, Charles University in Prague
Verified email at karlin.mff.cuni.cz
TitleCited byYear
Bounded arithmetic, propositional logic and complexity theory
J Krajicek, J Krajíček
Cambridge University Press, 1995
6331995
Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
J Krajíček
The Journal of Symbolic Logic 62 (2), 457-486, 1997
2581997
Propositional proof systems, the consistency of first order theories and the complexity of computations
J Krajíček, P Pudlák
The Journal of Symbolic Logic 54 (3), 1063-1079, 1989
1941989
Bounded arithmetic and the polynomial hierarchy
J Krajíček, P Pudlák, G Takeuti
Annals of Pure and Applied Logic 52 (1-2), 143-153, 1991
1781991
An exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle
J Krajíček, P Pudlák, A Woods
Random Structures & Algorithms 7 (1), 15-39, 1995
1621995
On the weak pigeonhole principle
J Krajícek
1492001
Lower bounds to the size of constant-depth propositional proofs
J Krajíček
The Journal of Symbolic Logic 59 (1), 73-86, 1994
1431994
Some Consequences of Cryptographical Conjectures forS12and EF
J Krajı́ček, P Pudlák
Information and Computation 140 (1), 82-94, 1998
133*1998
Lower bounds on Hilbert's Nullstellensatz and propositional proofs
P Beame, R Impagliazzo, J Krajíček, T Pitassi, P Pudlák
Proceedings of the London Mathematical Society 3 (1), 1-26, 1996
1211996
Exponential lower bounds for the pigeonhole principle
P Beame, R Impagliazzo, J Krajícek, T Pitassi, P Pudlák, A Woods
1181992
Quantified propositional calculi and fragments of bounded arithmetic
J Krajíček, P Pudlák
Zeitschrift für mathematische Logik und Grundlagen der Mathematik 36, 29-46, 1990
1051990
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
S Buss, R Impagliazzo, J Krajíček, P Pudlák, AA Razborov, J Sgall
Computational Complexity 6 (3), 256-298, 1996
1041996
An application of Boolean complexity to separation problems in bounded arithmetic
SR Buss, J Krajíček
Proceedings of the London Mathematical Society 3 (1), 1-21, 1994
931994
The number of proof lines and the size of proofs in first order logic
J Krajíček, P Pudlák
Archive for Mathematical Logic 27 (1), 69-84, 1988
891988
Lower bounds on Hilbert's Nullstellensatz and propositional proofs
P Beame, R Impagliazzo, J Krajícek, T Pitassi, P Pudlák
Proceedings 35th Annual Symposium on Foundations of Computer Science, 794-806, 1994
631994
Fragments of bounded arithmetic and bounded query classes
J Krajíček
Transactions of the American Mathematical Society 338 (2), 587-598, 1993
541993
On Frege and extended Frege proof systems
J Krajíček
Feasible Mathematics II, 284-319, 1995
501995
Combinatorics with definable sets: Euler characteristics and Grothendieck rings
J Krajíček, T Scanlon
Bulletin of Symbolic Logic 6 (3), 311-330, 2000
492000
Consequences of the provability of NPP/poly
S Cook, J Krajíček
The Journal of Symbolic Logic 72 (4), 1353-1371, 2007
442007
Forcing with random variables and proof complexity
J Krajíček
Cambridge University Press, 2010
432010
The system can't perform the operation now. Try again later.
Articles 1–20