dblp.uni-trier.dewww.uni-trier.de

Jan Krajícek

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo

2007
37EEJan 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)
36EEJan 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
34EEJan Krajícek: Forcing with Random Variables and Proof Complexity. CiE 2006: 277-278
2005
33EEJan Krajícek: Hardness assumptions in the foundations of theoretical computer science. Arch. Math. Log. 44(6): 667-675 (2005)
2004
32EEJan Krajícek: Combinatorics of first order structures and propositional proof systems. Arch. Math. Log. 43(4): 427-441 (2004)
31EEJan Krajícek: Diagonalization in proof complexity Electronic Colloquium on Computational Complexity (ECCC)(018): (2004)
2003
30EEJan Krajícek: Implicit proofs Electronic Colloquium on Computational Complexity (ECCC)(055): (2003)
29EEJan Krajícek: Dehn Function and Length of Proofs. IJAC 13(5): 527-541 (2003)
2002
28EERussell Impagliazzo, Jan Krajícek: A Note on Conservativity Relations among Bounded Arithmetic Theories. Math. Log. Q. 48(3): 375-377 (2002)
27EEJan Krajícek: Interpolation and Approximate Semantic Derivations. Math. Log. Q. 48(4): 602-606 (2002)
2001
26EEJan Krajícek: Tautologies from pseudo-random generators. Bulletin of Symbolic Logic 7(2): 197-212 (2001)
2000
25EEJan Krajícek, Thomas Scanlon: Combinatorics with definable sets: Euler characteristics and Grothendieck rings. Bulletin of Symbolic Logic 3(3): 311-330 (2000)
24EEJan Krajícek: Tautologies from pseudo-random generators Electronic Colloquium on Computational Complexity (ECCC) 7(33): (2000)
1999
23EEMario 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)
15EEJan 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
10EEJan 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)

Coauthor Index

1Matthias Baaz [18]
2Paul Beame [8] [12]
3Samuel R. Buss [16]
4Mario Chiari [21] [23]
5Petr Hájek [18]
6Russell Impagliazzo [8] [12] [16] [28]
7Toniann Pitassi [8] [12]
8Pavel Pudlák [1] [3] [5] [6] [8] [10] [11] [12] [13] [16] [22]
9Alexander A. Razborov [16]
10Thomas Scanlon [25]
11Jiri Sgall [5] [16]
12David Svejda [18]
13Gaisi Takeuti [6] [7]
14Alan R. Woods [8] [10] [13]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)