Bounded arithmetic, propositional logic and complexity theory J Krajicek Cambridge University Press, 1995 | 736 | 1995 |
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 | 341 | 1997 |
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 | 246 | 1989 |
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 | 219 | 1995 |
Bounded arithmetic and the polynomial hierarchy J Krajíček, P Pudlák, G Takeuti Annals of pure and applied logic 52 (1-2), 1991 | 205 | 1991 |
On the weak pigeonhole principle J Krajíček Fundamenta Mathematicae 170, 123-140, 2001 | 181 | 2001 |
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 | 174 | 1996 |
Lower bounds to the size of constant-depth propositional proofs J Krajíček The Journal of Symbolic Logic 59 (1), 73-86, 1994 | 169 | 1994 |
Some consequences of cryptographical conjectures fors12and ef J Krajı́ček, P Pudlák Information and Computation 140 (1), 82-94, 1998 | 163 | 1998 |
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 | 137 | 1992 |
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, 256-298, 1996 | 132 | 1996 |
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 | 126 | 1990 |
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 | 112 | 1994 |
The number of proof lines and the size of proofs in first order logic. J Krajícek, P Pudlák Arch. Math. Log. 27 (1), 69-84, 1988 | 107 | 1988 |
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 | 103 | 1994 |
Proof complexity J Krajíček Cambridge University Press, 2019 | 98 | 2019 |
Proof complexity J Krajıcek European congress of mathematics (ECM), Stockholm, Sweden, 221-231, 2004 | 93 | 2004 |
Consequences of the provability of NP⊆ P/poly S Cook, J Krajíček The Journal of Symbolic Logic 72 (4), 1353-1371, 2007 | 67 | 2007 |
Combinatorics with definable sets: Euler characteristics and Grothendieck rings J Krajíček, T Scanlon Bulletin of symbolic Logic 6 (3), 311-330, 2000 | 65 | 2000 |
Forcing with random variables and proof complexity J Krajíček Conference on Computability in Europe, 277-278, 2006 | 63 | 2006 |