Jan Krajicek
Jan Krajicek
Professor of Mathematical Logic, Charles University in Prague
Verified email at karlin.mff.cuni.cz
Title
Cited by
Cited by
Year
Bounded arithmetic, propositional logic and complexity theory
J Krajicek, J Krajíček
Cambridge University Press, 1995
6461995
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
2721997
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
2011989
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
1801991
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
1781995
On the weak pigeonhole principle
J Krajícek
1562001
Lower bounds to the size of constant-depth propositional proofs
J Krajíček
The Journal of Symbolic Logic 59 (1), 73-86, 1994
1471994
Some Consequences of Cryptographical Conjectures forS12and EF
J Krajı́ček, P Pudlák
Information and Computation 140 (1), 82-94, 1998
146*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
1341996
Exponential lower bounds for the pigeonhole principle
P Beame, R Impagliazzo, J Krajíček, T Pitassi, P Pudlák, A Woods
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing …, 1992
1231992
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
1111996
Quantified propositional calculi and fragments of bounded arithmetic
J Krajíček, P Pudlák
Zeitschrift für mathematische Logik und Grundlagen der Mathematik 36 (1), 29-46, 1990
1071990
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
951994
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
911988
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
691994
Combinatorics with definable sets: Euler characteristics and Grothendieck rings
J Krajíček, T Scanlon
Bulletin of symbolic Logic 6 (3), 311-330, 2000
542000
Fragments of bounded arithmetic and bounded query classes
J Krajíček
Transactions of the American Mathematical Society 338 (2), 587-598, 1993
541993
Forcing with random variables and proof complexity
J Krajíček
Cambridge University Press, 2010
522010
On Frege and extended Frege proof systems
J Krajíček
Feasible Mathematics II, 284-319, 1995
511995
Consequences of the provability of NPP/poly
S Cook, J Krajíček
The Journal of Symbolic Logic 72 (4), 1353-1371, 2007
472007
The system can't perform the operation now. Try again later.
Articles 1–20