| 2007 |
|---|
| 37 | EE | Jan Krajícek:
An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams.
Electronic Colloquium on Computational Complexity (ECCC) 14(007): (2007) |
| 36 | EE | Jan Krajícek:
Substitutions into propositional tautologies.
Inf. Process. Lett. 101(4): 163-167 (2007) |
| 2006 |
|---|
| 35 | | Jan Krajícek:
Proof Complexity Generators.
ACiD 2006: 3 |
| 34 | EE | Jan Krajícek:
Forcing with Random Variables and Proof Complexity.
CiE 2006: 277-278 |
| 2005 |
|---|
| 33 | EE | Jan Krajícek:
Hardness assumptions in the foundations of theoretical computer science.
Arch. Math. Log. 44(6): 667-675 (2005) |
| 2004 |
|---|
| 32 | EE | Jan Krajícek:
Combinatorics of first order structures and propositional proof systems.
Arch. Math. Log. 43(4): 427-441 (2004) |
| 31 | EE | Jan Krajícek:
Diagonalization in proof complexity
Electronic Colloquium on Computational Complexity (ECCC)(018): (2004) |
| 2003 |
|---|
| 30 | EE | Jan Krajícek:
Implicit proofs
Electronic Colloquium on Computational Complexity (ECCC)(055): (2003) |
| 29 | EE | Jan Krajícek:
Dehn Function and Length of Proofs.
IJAC 13(5): 527-541 (2003) |
| 2002 |
|---|
| 28 | EE | Russell Impagliazzo,
Jan Krajícek:
A Note on Conservativity Relations among Bounded Arithmetic Theories.
Math. Log. Q. 48(3): 375-377 (2002) |
| 27 | EE | Jan Krajícek:
Interpolation and Approximate Semantic Derivations.
Math. Log. Q. 48(4): 602-606 (2002) |
| 2001 |
|---|
| 26 | EE | Jan Krajícek:
Tautologies from pseudo-random generators.
Bulletin of Symbolic Logic 7(2): 197-212 (2001) |
| 2000 |
|---|
| 25 | EE | Jan Krajícek,
Thomas Scanlon:
Combinatorics with definable sets: Euler characteristics and Grothendieck rings.
Bulletin of Symbolic Logic 3(3): 311-330 (2000) |
| 24 | EE | Jan Krajícek:
Tautologies from pseudo-random generators
Electronic Colloquium on Computational Complexity (ECCC) 7(33): (2000) |
| 1999 |
|---|
| 23 | EE | Mario Chiari,
Jan Krajícek:
Lifting independence results in bounded arithmetic.
Arch. Math. Log. 38(2): 123-138 (1999) |
| 1998 |
|---|
| 22 | | Jan Krajícek,
Pavel Pudlák:
Some Consequences of Cryptographical Conjectures for S12 and EF.
Inf. Comput. 140(1): 82-94 (1998) |
| 21 | | Mario Chiari,
Jan Krajícek:
Witnessing Functions in Bounded Arithmetic and Search Problems.
J. Symb. Log. 63(3): 1095-1115 (1998) |
| 20 | | Jan Krajícek:
Discretely Ordered Modules as a First-Order Extension of The Cutting Planes Proof System.
J. Symb. Log. 63(4): 1582-1596 (1998) |
| 19 | | Jan Krajícek:
Interpolation by a Game.
Math. Log. Q. 44: 450-458 (1998) |
| 18 | | Matthias Baaz,
Petr Hájek,
David Svejda,
Jan Krajícek:
Embedding Logics into Product Logic.
Studia Logica 61(1): 35-47 (1998) |
| 1997 |
|---|
| 17 | | Jan Krajícek:
Lower Bounds for a Proof System with an Expentential Speed-up over Constant-Depth Frege Systems and over Polynomial Calculus.
MFCS 1997: 85-90 |
| 16 | | Samuel R. Buss,
Russell Impagliazzo,
Jan Krajícek,
Pavel Pudlák,
Alexander A. Razborov,
Jiri Sgall:
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.
Computational Complexity 6(3): 256-298 (1997) |
| 15 | EE | Jan Krajícek:
Interpolation by a Game
Electronic Colloquium on Computational Complexity (ECCC) 4(15): (1997) |
| 14 | | Jan Krajícek:
Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic.
J. Symb. Log. 62(2): 457-486 (1997) |
| 1995 |
|---|
| 13 | | Jan Krajícek,
Pavel Pudlák,
Alan R. Woods:
An Exponenetioal Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle.
Random Struct. Algorithms 7(1): 15-40 (1995) |
| 1994 |
|---|
| 12 | | Paul Beame,
Russell Impagliazzo,
Jan Krajícek,
Toniann Pitassi,
Pavel Pudlák:
Lower Bound on Hilbert's Nullstellensatz and propositional proofs
FOCS 1994: 794-806 |
| 11 | | Jan Krajícek,
Pavel Pudlák:
Some Consequences of Cryptographical Conjectures for S_2^1 and EF.
LCC 1994: 210-220 |
| 10 | EE | Jan Krajícek,
Pavel Pudlák,
Alan R. Woods:
An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle
Electronic Colloquium on Computational Complexity (ECCC) 1(18): (1994) |
| 9 | | Jan Krajícek:
Lower Bounds to the Size of Constant-Depth Propositional Proofs.
J. Symb. Log. 59(1): 73-86 (1994) |
| 1992 |
|---|
| 8 | | Paul Beame,
Russell Impagliazzo,
Jan Krajícek,
Toniann Pitassi,
Pavel Pudlák,
Alan R. Woods:
Exponential Lower Bounds for the Pigeonhole Principle
STOC 1992: 200-220 |
| 7 | | Jan Krajícek,
Gaisi Takeuti:
On Induction-Free Provability.
Ann. Math. Artif. Intell. 6(1-3): 107-125 (1992) |
| 1991 |
|---|
| 6 | | Jan Krajícek,
Pavel Pudlák,
Gaisi Takeuti:
Bounded Arithmetic and the Polynomial Hierarchy.
Ann. Pure Appl. Logic 52(1-2): 143-153 (1991) |
| 1990 |
|---|
| 5 | | Jan Krajícek,
Pavel Pudlák,
Jiri Sgall:
Interactive Computations of Optimal Solutions.
MFCS 1990: 48-60 |
| 4 | | Jan Krajícek:
Exponentiation and Second-Order Bounded Arithmetic.
Ann. Pure Appl. Logic 48(3): 261-276 (1990) |
| 1989 |
|---|
| 3 | | Jan Krajícek,
Pavel Pudlák:
Propositional Provability and Models of Weak Arithmetic.
CSL 1989: 193-210 |
| 2 | | Jan Krajícek:
On the Number of Steps in Proofs.
Ann. Pure Appl. Logic 41(2): 153-178 (1989) |
| 1 | | Jan Krajícek,
Pavel Pudlák:
Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations.
J. Symb. Log. 54(3): 1063-1079 (1989) |
