×

zbMATH — the first resource for mathematics

Krajíček, Jan

Compute Distance To:
Author ID: krajicek.jan Recent zbMATH articles by "Krajíček, Jan"
Published as: Krajicek, Jan; Krajiček, Jan; Krajíček, J.; Krajíček, Jan
Documents Indexed: 85 Publications since 1984, including 6 Books

Publications by Year

Citations contained in zbMATH Open

67 Publications have been cited 800 times in 383 Documents Cited by Year
Bounded arithmetic, propositional logic, and complexity theory. Zbl 0835.03025
Krajíček, Jan
123
1995
Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. Zbl 0891.03029
Krajíček, Jan
67
1997
Propositional proof systems, the consistency of first order theories and the complexity of computations. Zbl 0696.03029
Krajíček, Jan; Pudlák, Pavel
48
1989
Bounded arithmetic and the polynomial hierarchy. Zbl 0736.03022
Krajíček, Jan; Pudlák, Pavel; Takeuti, Gaisi
42
1991
On the weak pigeonhole principle. Zbl 0987.03051
Krajíček, Jan
39
2001
Lower bounds to the size of constant-depth propositional proofs. Zbl 0798.03056
Krajíček, Jan
38
1994
An exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Zbl 0843.03032
Krajíček, Jan; Pudlák, Pavel; Woods, Alan
35
1995
Some consequences of cryptographical conjectures for \(S_2^1\) and EF. Zbl 0892.68029
Krajíček, Jan; Pudlák, Pavel
28
1998
The number of proof lines and the size of proofs in first order logic. Zbl 0644.03032
Krajíček, Jan; Pudlák, Pavel
28
1988
Quantified propositional calculi and fragments of bounded arithmetic. Zbl 0696.03031
Krajíček, Jan; Pudlák, Pavel
26
1990
Lower bounds on Hilbert’s Nullstellensatz and propositional proofs. Zbl 0853.03017
Beame, Paul; Impagliazzo, Russell; Krajíček, Jan; Pitassi, Toniann; Pudlák, Pavel
25
1996
An application of Boolean complexity to separation problems in bounded arithmetic. Zbl 0799.03066
Buss, Samuel R.; Krajíček, Jan
22
1994
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Zbl 0890.03030
Buss, S.; Impagliazzo, R.; Krajíček, J.; Pudlák, P.; Razborov, A. A.; Sgall, J.
19
1997
Combinatorics with definable sets: Euler characteristics and Grothendieck rings. Zbl 0968.03036
Krajíček, Jan; Scanlon, Thomas
17
2000
NP search problems in low fragments of bounded arithmetic. Zbl 1118.03051
Krajíček, Jan; Skelley, Alan; Thapen, Neil
15
2007
Consequences of the provability of \(\mathrm{NP}\subseteq \mathrm{P/poly}\). Zbl 1133.03035
Cook, Stephen; Krajíček, Jan
12
2007
Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds. Zbl 1068.03048
Krajíček, Jan
12
2004
An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams. Zbl 1141.03028
Krajíček, Jan
11
2008
On the number of steps in proofs. Zbl 0672.03042
Krajíček, Jan
11
1989
A note on proofs of falsehood. Zbl 0633.03056
Krajíček, Jan
11
1987
Tautologies from pseudo-random generators. Zbl 0983.03046
Krajíček, Jan
9
2001
Fragments of bounded arithmetic and bounded query classes. Zbl 0787.03047
Krajíček, Jan
9
1993
Forcing with random variables and proof complexity. Zbl 1219.03071
Krajíček, Jan
8
2011
Generalizations of proofs. Zbl 0644.03031
Krajíček, Jan
8
1987
Arithmetic, proof theory, and computational complexity. Zbl 0777.00008
Clote, Peter (ed.); Krajíček, Jan (ed.)
7
1993
On induction-free provability. Zbl 0865.03045
Krajíček, Jan; Takeuti, Gaisi
7
1992
Combinatorics of first order structures and propositional proof systems. Zbl 1061.03060
Krajíček, Jan
6
2004
Discretely ordered modules as a first-order extension of the cutting planes proof system. Zbl 0930.03081
Krajíček, Jan
6
1998
Witnessing functions in bounded arithmetic and search problems. Zbl 0919.03044
Chiari, Mario; Krajiček, Jan
6
1998
Exponentiation and second-order bounded arithmetic. Zbl 0711.03025
Krajíček, Jan
6
1990
Implicit proofs. Zbl 1069.03053
Krajíček, Jan
5
2004
A note on conservativity relations among bounded arithmetic theories. Zbl 0997.03046
Impagliazzo, Russell; Krajíček, Jan
5
2002
Uniform families of polynomial equations over a finite field and structures admitting an Euler characteristic of definable sets. Zbl 1034.03045
Krajíček, Jan
5
2000
Lifting independence results in bounded arithmetic. Zbl 0924.03107
Chiari, Mario; Krajíček, Jan
5
1999
Embedding logics into product logic. Zbl 0962.03019
Baaz, Matthias; Hájek, Petr; Krajíček, Jan; Švejda, David
5
1998
Interpolation by a game. Zbl 0915.03047
Krajíček, Jan
5
1998
No counter-example interpretation and interactive computation. Zbl 0752.03028
Krajíček, Jan
5
1992
Diagonalization in proof complexity. Zbl 1068.03049
Krajíček, Jan
4
2004
Extensions of models of PV. Zbl 0897.03054
Krajíček, Jan
4
1998
Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus. Zbl 0935.03068
Krajíček, Jan
4
1997
On methods for proving lower bounds in propositional logic. Zbl 0907.03024
Krajíček, Jan
4
1997
On Frege and extended Frege proof systems. Zbl 0843.03033
Krajíček, Jan
4
1995
On the proof complexity of the Nisan-Wigderson generator based on a hard \(\mathrm{NP} \cap \mathrm{coNP}\) function. Zbl 1259.03073
Krajíček, Jan
3
2011
A note on propositional proof complexity of some Ramsey-type statements. Zbl 1231.03050
Krajíček, Jan
3
2011
Structured pigeonhole principle, search problems and hard tautologies. Zbl 1089.03049
Krajíček, Jan
3
2005
On the degree of ideal membership proofs from uniform families of polynomials over a finite field. Zbl 0984.03044
Krajíček, Jan
3
2001
Provably total function in bounded arithmetic theories \(R_ 3^ i\), \(U_ 2^ i\) and \(V_ 2^ i\). Zbl 0799.03065
Buss, Samuel R.; Krajíček, Jan; Takeuti, Gaisi
3
1993
Propositional provability and models of weak arithmetic. Zbl 0925.03211
Krajíček, Jan; Pudlák, Pavel
3
1990
Proof complexity. Zbl 07044161
Krajíček, Jan
2
2019
Randomized feasible interpolation and monotone circuits with a local oracle. Zbl 06996246
Krajíček, Jan
2
2018
Proof complexity. Zbl 1089.03050
Krajíček, Jan
2
2005
Approximate Euler characteristic, dimension, and weak pigeonhole principles. Zbl 1068.03024
Krajíček, Jan
2
2004
Speed-up for propositional Frege systems via generalizations of proofs. Zbl 0675.03034
Krajíček, Jan
2
1989
Some results and problems in the modal set theory MST. Zbl 0654.03012
Krajíček, Jan
2
1988
A possible modal formulation of comprehension scheme. Zbl 0644.03027
Krajíček, Jan
2
1987
On monotone circuits with local oracles and clique lower bounds. Zbl 1398.68163
Krajíček, Jan; Oliveira, Igor C.
1
2018
A feasible interpolation for random resolution. Zbl 1448.03047
Krajicek, Jan
1
2017
Unprovability of circuit upper bounds in Cook’s theory PV. Zbl 1448.03048
Krajicek, Jan; Oliveira, Igor C.
1
2017
Consistency of circuit evaluation, extended resolution and total NP search problems. Zbl 1402.03082
Krajíček, Jan
1
2016
A form of feasible interpolation for constant depth Frege systems. Zbl 1194.03052
Krajíček, Jan
1
2010
A proof complexity generator. Zbl 1419.03052
Krajíček, Jan
1
2009
Complexity of computations and proofs. Zbl 1062.68004
Krajíček, Jan (ed.)
1
2004
Dehn function and length of proofs. Zbl 1043.03045
Krajíček, Jan
1
2003
Interpolation and approximate semantic derivations. Zbl 1013.03069
Krajíček, Jan
1
2002
A fundamental problem of mathematical logic. Zbl 0858.03040
Krajíček, Jan
1
1996
On bounded \(\Sigma{}_ 1^ 1\) polynomial induction. Zbl 0764.03022
Krajíček, Jan; Takeuti, Gaisi
1
1990
On the structure of initial segments of models of arithmetic. Zbl 0678.03026
Krajíček, Jan; Pudlák, Pavel
1
1989
Proof complexity. Zbl 07044161
Krajíček, Jan
2
2019
Randomized feasible interpolation and monotone circuits with a local oracle. Zbl 06996246
Krajíček, Jan
2
2018
On monotone circuits with local oracles and clique lower bounds. Zbl 1398.68163
Krajíček, Jan; Oliveira, Igor C.
1
2018
A feasible interpolation for random resolution. Zbl 1448.03047
Krajicek, Jan
1
2017
Unprovability of circuit upper bounds in Cook’s theory PV. Zbl 1448.03048
Krajicek, Jan; Oliveira, Igor C.
1
2017
Consistency of circuit evaluation, extended resolution and total NP search problems. Zbl 1402.03082
Krajíček, Jan
1
2016
Forcing with random variables and proof complexity. Zbl 1219.03071
Krajíček, Jan
8
2011
On the proof complexity of the Nisan-Wigderson generator based on a hard \(\mathrm{NP} \cap \mathrm{coNP}\) function. Zbl 1259.03073
Krajíček, Jan
3
2011
A note on propositional proof complexity of some Ramsey-type statements. Zbl 1231.03050
Krajíček, Jan
3
2011
A form of feasible interpolation for constant depth Frege systems. Zbl 1194.03052
Krajíček, Jan
1
2010
A proof complexity generator. Zbl 1419.03052
Krajíček, Jan
1
2009
An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams. Zbl 1141.03028
Krajíček, Jan
11
2008
NP search problems in low fragments of bounded arithmetic. Zbl 1118.03051
Krajíček, Jan; Skelley, Alan; Thapen, Neil
15
2007
Consequences of the provability of \(\mathrm{NP}\subseteq \mathrm{P/poly}\). Zbl 1133.03035
Cook, Stephen; Krajíček, Jan
12
2007
Structured pigeonhole principle, search problems and hard tautologies. Zbl 1089.03049
Krajíček, Jan
3
2005
Proof complexity. Zbl 1089.03050
Krajíček, Jan
2
2005
Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds. Zbl 1068.03048
Krajíček, Jan
12
2004
Combinatorics of first order structures and propositional proof systems. Zbl 1061.03060
Krajíček, Jan
6
2004
Implicit proofs. Zbl 1069.03053
Krajíček, Jan
5
2004
Diagonalization in proof complexity. Zbl 1068.03049
Krajíček, Jan
4
2004
Approximate Euler characteristic, dimension, and weak pigeonhole principles. Zbl 1068.03024
Krajíček, Jan
2
2004
Complexity of computations and proofs. Zbl 1062.68004
Krajíček, Jan (ed.)
1
2004
Dehn function and length of proofs. Zbl 1043.03045
Krajíček, Jan
1
2003
A note on conservativity relations among bounded arithmetic theories. Zbl 0997.03046
Impagliazzo, Russell; Krajíček, Jan
5
2002
Interpolation and approximate semantic derivations. Zbl 1013.03069
Krajíček, Jan
1
2002
On the weak pigeonhole principle. Zbl 0987.03051
Krajíček, Jan
39
2001
Tautologies from pseudo-random generators. Zbl 0983.03046
Krajíček, Jan
9
2001
On the degree of ideal membership proofs from uniform families of polynomials over a finite field. Zbl 0984.03044
Krajíček, Jan
3
2001
Combinatorics with definable sets: Euler characteristics and Grothendieck rings. Zbl 0968.03036
Krajíček, Jan; Scanlon, Thomas
17
2000
Uniform families of polynomial equations over a finite field and structures admitting an Euler characteristic of definable sets. Zbl 1034.03045
Krajíček, Jan
5
2000
Lifting independence results in bounded arithmetic. Zbl 0924.03107
Chiari, Mario; Krajíček, Jan
5
1999
Some consequences of cryptographical conjectures for \(S_2^1\) and EF. Zbl 0892.68029
Krajíček, Jan; Pudlák, Pavel
28
1998
Discretely ordered modules as a first-order extension of the cutting planes proof system. Zbl 0930.03081
Krajíček, Jan
6
1998
Witnessing functions in bounded arithmetic and search problems. Zbl 0919.03044
Chiari, Mario; Krajiček, Jan
6
1998
Embedding logics into product logic. Zbl 0962.03019
Baaz, Matthias; Hájek, Petr; Krajíček, Jan; Švejda, David
5
1998
Interpolation by a game. Zbl 0915.03047
Krajíček, Jan
5
1998
Extensions of models of PV. Zbl 0897.03054
Krajíček, Jan
4
1998
Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. Zbl 0891.03029
Krajíček, Jan
67
1997
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Zbl 0890.03030
Buss, S.; Impagliazzo, R.; Krajíček, J.; Pudlák, P.; Razborov, A. A.; Sgall, J.
19
1997
Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus. Zbl 0935.03068
Krajíček, Jan
4
1997
On methods for proving lower bounds in propositional logic. Zbl 0907.03024
Krajíček, Jan
4
1997
Lower bounds on Hilbert’s Nullstellensatz and propositional proofs. Zbl 0853.03017
Beame, Paul; Impagliazzo, Russell; Krajíček, Jan; Pitassi, Toniann; Pudlák, Pavel
25
1996
A fundamental problem of mathematical logic. Zbl 0858.03040
Krajíček, Jan
1
1996
Bounded arithmetic, propositional logic, and complexity theory. Zbl 0835.03025
Krajíček, Jan
123
1995
An exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Zbl 0843.03032
Krajíček, Jan; Pudlák, Pavel; Woods, Alan
35
1995
On Frege and extended Frege proof systems. Zbl 0843.03033
Krajíček, Jan
4
1995
Lower bounds to the size of constant-depth propositional proofs. Zbl 0798.03056
Krajíček, Jan
38
1994
An application of Boolean complexity to separation problems in bounded arithmetic. Zbl 0799.03066
Buss, Samuel R.; Krajíček, Jan
22
1994
Fragments of bounded arithmetic and bounded query classes. Zbl 0787.03047
Krajíček, Jan
9
1993
Arithmetic, proof theory, and computational complexity. Zbl 0777.00008
Clote, Peter (ed.); Krajíček, Jan (ed.)
7
1993
Provably total function in bounded arithmetic theories \(R_ 3^ i\), \(U_ 2^ i\) and \(V_ 2^ i\). Zbl 0799.03065
Buss, Samuel R.; Krajíček, Jan; Takeuti, Gaisi
3
1993
On induction-free provability. Zbl 0865.03045
Krajíček, Jan; Takeuti, Gaisi
7
1992
No counter-example interpretation and interactive computation. Zbl 0752.03028
Krajíček, Jan
5
1992
Bounded arithmetic and the polynomial hierarchy. Zbl 0736.03022
Krajíček, Jan; Pudlák, Pavel; Takeuti, Gaisi
42
1991
Quantified propositional calculi and fragments of bounded arithmetic. Zbl 0696.03031
Krajíček, Jan; Pudlák, Pavel
26
1990
Exponentiation and second-order bounded arithmetic. Zbl 0711.03025
Krajíček, Jan
6
1990
Propositional provability and models of weak arithmetic. Zbl 0925.03211
Krajíček, Jan; Pudlák, Pavel
3
1990
On bounded \(\Sigma{}_ 1^ 1\) polynomial induction. Zbl 0764.03022
Krajíček, Jan; Takeuti, Gaisi
1
1990
Propositional proof systems, the consistency of first order theories and the complexity of computations. Zbl 0696.03029
Krajíček, Jan; Pudlák, Pavel
48
1989
On the number of steps in proofs. Zbl 0672.03042
Krajíček, Jan
11
1989
Speed-up for propositional Frege systems via generalizations of proofs. Zbl 0675.03034
Krajíček, Jan
2
1989
On the structure of initial segments of models of arithmetic. Zbl 0678.03026
Krajíček, Jan; Pudlák, Pavel
1
1989
The number of proof lines and the size of proofs in first order logic. Zbl 0644.03032
Krajíček, Jan; Pudlák, Pavel
28
1988
Some results and problems in the modal set theory MST. Zbl 0654.03012
Krajíček, Jan
2
1988
A note on proofs of falsehood. Zbl 0633.03056
Krajíček, Jan
11
1987
Generalizations of proofs. Zbl 0644.03031
Krajíček, Jan
8
1987
A possible modal formulation of comprehension scheme. Zbl 0644.03027
Krajíček, Jan
2
1987
all top 5

Cited by 303 Authors

32 Krajíček, Jan
24 Beyersdorff, Olaf
21 Pudlák, Pavel
17 Buss, Samuel R.
14 Thapen, Neil
13 Jeřábek, Emil
12 Lauria, Massimo
11 Beckmann, Arnold
11 Kołodziejczyk, Leszek Aleksander
9 Baaz, Matthias
9 Galesi, Nicola
8 Atserias, Albert
8 Pitassi, Toniann
7 Buss, Sam
7 Müller, Moritz
7 Razborov, Aleksandr Aleksandrovich
7 Willard, Dan E.
6 Bonet, Maria Luisa
6 Cook, Stephen Arthur
6 Pollett, Chris
6 Visser, Albert
5 Hirsch, Edward A.
5 Hrubeš, Pavel
5 Itsykson, Dmitry M.
5 Müller, Sebastian
5 Takeuti, Gaisi
5 Tzameret, Iddo
5 Urquhart, Alasdair
4 Ferreira, Fernando
4 Grigor’ev, Dmitriĭ Yur’evich
4 Impagliazzo, Russell
4 Köbler, Johannes
4 Pich, Ján
4 Sadowski, Zenon
4 Sokolev, Dmitry
4 Straßburger, Lutz
3 Adamowicz, Zofia
3 Arai, Noriko H.
3 Arai, Toshiyasu
3 Blinkhorn, Joshua
3 Carbone, Antonio
3 Chen, Yijia
3 Chew, Leroy
3 Clote, Peter G.
3 Dantchev, Stefan Stoyanov
3 Flum, Jörg
3 Hetzl, Stefan
3 Hinde, Luke
3 Istrate, Gabriel I.
3 Janota, Mikoláš
3 Kuber, Amit
3 Marques-Silva, João P.
3 Martin, Barnaby D.
3 Messner, Jochen
3 Nordström, Jakob
3 Sofronie-Stokkermans, Viorica
3 Zambella, Domenico
2 Aehlig, Klaus
2 Aisenberg, James
2 Alekhnovich, Michael
2 Beame, Paul W.
2 Bonacina, Maria Paola
2 Cavagnetto, Stefano
2 Chinchilla, Eugenio
2 Ciabattoni, Agata
2 Cluckers, Raf
2 Crǎciun, Adrian
2 Dose, Titus
2 Eberhard, Sebastian
2 Esteban, Juan Luis
2 Farmer, William M.
2 Filmus, Yuval
2 Garlík, Michal
2 Goldberg, Paul W.
2 Iwama, Kazuo
2 Johannsen, Jan
2 Johansson, Moa
2 Kullmann, Oliver
2 Li, Fu
2 Lopes, Vinicius Cifú
2 Maciel, Alexis
2 Mahajan, Meena
2 McMillan, Kenneth L.
2 Moniri, Morteza
2 Naumov, Pavel G.
2 Nguyen, Phuong Ha
2 Papadimitriou, Christos Harilaos
2 Preining, Norbert
2 Raz, Ran
2 Riis, Søren
2 Şhukla, Anil K.
2 Smal, Alexander V.
2 Szeider, Stefan
2 Zhang, Wenhui
1 Aguzzoli, Stefano
1 Allen, Bill
1 Allender, Eric W.
1 Alrajeh, Dalal
1 Amir, Eyal
1 Anjos, Miguel F.
...and 203 more Authors
all top 5

Cited in 56 Serials

65 Annals of Pure and Applied Logic
41 The Journal of Symbolic Logic
36 Archive for Mathematical Logic
27 Theoretical Computer Science
18 Mathematical Logic Quarterly (MLQ)
16 Information and Computation
15 Information Processing Letters
14 The Bulletin of Symbolic Logic
9 Journal of Computer and System Sciences
9 Computational Complexity
7 Artificial Intelligence
6 Annals of Mathematics and Artificial Intelligence
6 Theory of Computing Systems
6 ACM Transactions on Computational Logic
5 Notre Dame Journal of Formal Logic
5 Logical Methods in Computer Science
4 Journal of Algebra
4 Journal of Mathematical Sciences (New York)
3 Journal of Symbolic Computation
3 Journal of Automated Reasoning
3 Journal of Mathematical Logic
2 Discrete Applied Mathematics
2 Journal of Philosophical Logic
2 Journal of Pure and Applied Algebra
2 Proceedings of the American Mathematical Society
2 SIAM Journal on Computing
2 Studia Logica
2 Transactions of the American Mathematical Society
2 Operations Research Letters
2 Bulletin of Mathematical Sciences
2 Theory of Computing
1 Annals of Science
1 Mathematical Proceedings of the Cambridge Philosophical Society
1 Fundamenta Mathematicae
1 Fuzzy Sets and Systems
1 Journal of Soviet Mathematics
1 Mathematische Zeitschrift
1 Combinatorica
1 Annals of Operations Research
1 Random Structures & Algorithms
1 International Journal of Algebra and Computation
1 MSCS. Mathematical Structures in Computer Science
1 International Journal of Foundations of Computer Science
1 Formal Methods in System Design
1 Constraints
1 Soft Computing
1 Journal of Combinatorial Optimization
1 Journal of the ACM
1 Annals of Mathematics. Second Series
1 Logic and Logical Philosophy
1 Portugaliae Mathematica. Nova Série
1 Journal of Applied Mathematics and Computing
1 Logica Universalis
1 The Review of Symbolic Logic
1 Forum of Mathematics, Sigma
1 Philosophical Transactions of the Royal Society of London. A. Mathematical, Physical and Engineering Sciences

Citations by Year