default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDJan Krajícek
Person information
- affiliation: Charles University, Faculty of Mathematics and Physics, Prague, Czech Republic
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
[j52]Jan Krajícek
:
On the existence of Strong Proof Complexity Generators. Bull. Symb. Log. 30(1): 20-40 (2024)- 2023
- [p1]Jan Krajícek:
The Cook-Reckhow Definition. Logic, Automata, and Computational Complexity 2023: 83-94 - [i29]Jan Krajícek:
Extended Nullstellensatz proof systems. CoRR abs/2301.10617 (2023) - [i28]Jan Krajícek:
A proof complexity conjecture and the Incompleteness theorem. CoRR abs/2303.10637 (2023) - [i27]Jan Krajícek:
Extended Nullstellensatz proof systems. Electron. Colloquium Comput. Complex. TR23 (2023) - [i26]Jan Krajícek:
A proof complexity conjecture and the Incompleteness theorem. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j51]Jan Krajícek:
Information in Propositional Proofs and Algorithmic Proof Search. J. Symb. Log. 87(2): 852-869 (2022) - [i25]Jan Krajícek:
On the existence of strong proof complexity generators. CoRR abs/2208.11642 (2022) - [i24]Jan Krajícek:
On the existence of strong proof complexity generators. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j50]Jan Krajícek:
Small Circuits and Dual Weak PHP in the Universal Theory of p-time Algorithms. ACM Trans. Comput. Log. 22(2): 11:1-11:4 (2021) - [i23]Jan Krajícek:
Information in propositional proofs and algorithmic proof search. CoRR abs/2104.04711 (2021) - [i22]Jan Krajícek:
Information in propositional proofs and algorithmic proof search. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j49]Jan Bydzovsky, Jan Krajícek, Igor C. Oliveira:
Consistency of circuit lower bounds with bounded theories. Log. Methods Comput. Sci. 16(2) (2020) - [j48]Jan Krajícek:
A limitation on the KPT interpolation. Log. Methods Comput. Sci. 16(3) (2020) - [i21]Jan Krajícek:
A limitation on the KPT interpolation. CoRR abs/2004.02448 (2020) - [i20]Jan Krajícek:
Small circuits and dual weak PHP in the universal theory of p-time algorithms. CoRR abs/2004.11582 (2020)
2010 – 2019
- 2019
- [i19]Jan Bydzovsky, Jan Krajícek, Igor C. Oliveira:
Consistency of circuit lower bounds with bounded theories. CoRR abs/1905.12935 (2019) - [i18]Jan Krajícek:
The Cook-Reckhow definition. CoRR abs/1909.03691 (2019) - [i17]Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajícek:
Consistency of circuit lower bounds with bounded theories. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j47]Jan Krajícek, Igor C. Oliveira:
On monotone circuits with local oracles and clique lower bounds. Chic. J. Theor. Comput. Sci. 2018 (2018) - [j46]Jan Krajícek:
Randomized feasible interpolation and monotone circuits with a local oracle. J. Math. Log. 18(2): 1850012:1-1850012:27 (2018) - 2017
- [j45]Jan Krajícek:
A feasible interpolation for random resolution. Log. Methods Comput. Sci. 13(1) (2017) - [j44]Jan Krajícek, Igor C. Oliveira:
Unprovability of circuit upper bounds in Cook's theory PV. Log. Methods Comput. Sci. 13(1) (2017) - [i16]Jan Krajícek, Igor C. Oliveira:
On monotone circuits with local oracles and clique lower bounds. CoRR abs/1704.06241 (2017) - 2016
- [i15]Jan Krajícek:
Randomized feasible interpolation and monotone circuits with a local oracle. CoRR abs/1611.08680 (2016) - [i14]Jan Krajícek, Igor Carboni Oliveira:
Unprovability of circuit upper bounds in Cook's theory PV. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [i13]Jan Krajícek:
Expansions of pseudofinite structures and circuit and proof complexity. CoRR abs/1505.00118 (2015) - [i12]Jan Krajícek:
Consistency of circuit evaluation, extended resolution and total NP search problems. CoRR abs/1509.03048 (2015) - 2014
- [i11]Olaf Beyersdorff, Edward A. Hirsch, Jan Krajícek, Rahul Santhanam:
Optimal algorithms and proofs (Dagstuhl Seminar 14421). Dagstuhl Reports 4(10): 51-68 (2014) - 2013
- [j43]Jan Krajícek:
A saturation property of structures obtained by forcing with a compact family of random variables. Arch. Math. Log. 52(1-2): 19-28 (2013) - [i10]Jan Krajícek:
A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems. CoRR abs/1311.2501 (2013) - [i9]Jan Krajícek:
A reduction of proof complexity to computational complexity for AC0[p] Frege systems. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j42]Jan Krajícek:
Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator. Log. Methods Comput. Sci. 8(3) (2012) - [j41]Jan Krajícek:
A note on SAT algorithms and proof complexity. Inf. Process. Lett. 112(12): 490-493 (2012) - [i8]Jan Krajícek:
On the computational complexity of finding hard tautologies. CoRR abs/1212.1789 (2012) - 2011
- [b2]Jan Krajícek:
Forcing with Random Variables and Proof Complexity. London Mathematical Society lecture note series 382, Cambridge University Press 2011, ISBN 978-0-521-15433-8, pp. I-XVI, 1-247 - [j40]Jan Krajícek:
A note on propositional proof complexity of some Ramsey-type statements. Arch. Math. Log. 50(1-2): 245-255 (2011) - [j39]Jan Krajícek:
On the Proof Complexity of the Nisan-Wigderson Generator based on a Hard NP ∩ coNP function. J. Math. Log. 11(1) (2011) - 2010
- [j38]Jan Krajícek:
A form of feasible interpolation for constant depth Frege systems. J. Symb. Log. 75(2): 774-784 (2010) - [c10]Jan Krajícek:
From Feasible Proofs to Feasible Computations. CSL 2010: 22-31 - [i7]Jan Krajícek:
On the proof complexity of the Nisan-Wigderson generator based on a hard NP cap coNP function. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2008
- [j37]Jan Krajícek:
An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams. J. Symb. Log. 73(1): 227-237 (2008) - 2007
- [j36]Jan Krajícek:
Substitutions into propositional tautologies. Inf. Process. Lett. 101(4): 163-167 (2007) - [j35]Jan Krajícek, Alan Skelley, Neil Thapen:
NP search problems in low fragments of bounded arithmetic. J. Symb. Log. 72(2): 649-672 (2007) - [j34]Stephen A. Cook, Jan Krajícek:
Consequences of the provability of NP ⊆ P/poly. J. Symb. Log. 72(4): 1353-1371 (2007) - [i6]Jan Krajícek:
An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [c9]Jan Krajícek:
Proof Complexity Generators. ACiD 2006: 3 - [c8]Jan Krajícek:
Forcing with Random Variables and Proof Complexity. CiE 2006: 277-278 - 2005
- [j33]Jan Krajícek:
Hardness assumptions in the foundations of theoretical computer science. Arch. Math. Log. 44(6): 667-675 (2005) - [j32]Jan Krajícek:
Structured pigeonhole principle, search problems and hard tautologies. J. Symb. Log. 70(2): 619-630 (2005) - 2004
- [j31]Jan Krajícek:
Combinatorics of first order structures and propositional proof systems. Arch. Math. Log. 43(4): 427-441 (2004) - [j30]Jan Krajícek:
Approximate Euler characteristic, dimension, and weak pigeonhole principles. J. Symb. Log. 69(1): 201-214 (2004) - [j29]Jan Krajícek:
Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds. J. Symb. Log. 69(1): 265-286 (2004) - [j28]Jan Krajícek:
Implicit proofs. J. Symb. Log. 69(2): 387-397 (2004) - [i5]Jan Krajícek:
Diagonalization in proof complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j27]Jan Krajícek:
Dehn Function and Length of Proofs. Int. J. Algebra Comput. 13(5): 527-541 (2003) - [i4]Jan Krajícek:
Implicit proofs. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [j26]Russell Impagliazzo, Jan Krajícek:
A Note on Conservativity Relations among Bounded Arithmetic Theories. Math. Log. Q. 48(3): 375-377 (2002) - [j25]Jan Krajícek:
Interpolation and Approximate Semantic Derivations. Math. Log. Q. 48(4): 602-606 (2002) - 2001
- [j24]Jan Krajícek:
Tautologies from pseudo-random generators. Bull. Symb. Log. 7(2): 197-212 (2001) - 2000
- [j23]Jan Krajícek, Thomas Scanlon:
Combinatorics with definable sets: Euler characteristics and Grothendieck rings. Bull. Symb. Log. 6(3): 311-330 (2000) - [i3]Jan Krajícek:
Tautologies from pseudo-random generators. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [j22]Mario Chiari, Jan Krajícek:
Lifting independence results in bounded arithmetic. Arch. Math. Log. 38(2): 123-138 (1999) - 1998
- [j21]Jan Krajícek, Pavel Pudlák:
Some Consequences of Cryptographical Conjectures for S12 and EF. Inf. Comput. 140(1): 82-94 (1998) - [j20]Mario Chiari, Jan Krajícek:
Witnessing Functions in Bounded Arithmetic and Search Problems. J. Symb. Log. 63(3): 1095-1115 (1998) - [j19]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) - [j18]Jan Krajícek:
Interpolation by a Game. Math. Log. Q. 44: 450-458 (1998) - [j17]Matthias Baaz, Petr Hájek, David Svejda, Jan Krajícek:
Embedding Logics into Product Logic. Stud Logica 61(1): 35-47 (1998) - 1997
- [j16]Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jirí Sgall:
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Comput. Complex. 6(3): 256-298 (1997) - [j15]Jan Krajícek:
Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic. J. Symb. Log. 62(2): 457-486 (1997) - [c7]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 - [i2]Jan Krajícek:
Interpolation by a Game. Electron. Colloquium Comput. Complex. TR97 (1997) - 1995
- [b1]Jan Krajícek:
Bounded arithmetic, propositional logic, and complexity theory. Encyclopedia of mathematics and its applications 60, Cambridge University Press 1995, ISBN 978-0-521-45205-2, pp. I-XIII, 1-343 - [j14]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) - [c6]Jan Krajícek:
Extensions of Models of PV. Logic Colloquium 1995: 104-114 - 1994
- [j13]Jan Krajícek:
Lower Bounds to the Size of Constant-Depth Propositional Proofs. J. Symb. Log. 59(1): 73-86 (1994) - [c5]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 - [c4]Jan Krajícek, Pavel Pudlák:
Some Consequences of Cryptographical Conjectures for S_2^1 and EF. LCC 1994: 210-220 - [i1]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. Electron. Colloquium Comput. Complex. TR94 (1994) - 1992
- [j12]Jan Krajícek, Gaisi Takeuti:
On Induction-Free Provability. Ann. Math. Artif. Intell. 6(1-3): 107-125 (1992) - [c3]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 - 1991
- [j11]Jan Krajícek, Pavel Pudlák, Gaisi Takeuti:
Bounded Arithmetic and the Polynomial Hierarchy. Ann. Pure Appl. Log. 52(1-2): 143-153 (1991) - 1990
- [j10]Jan Krajícek:
Exponentiation and Second-Order Bounded Arithmetic. Ann. Pure Appl. Log. 48(3): 261-276 (1990) - [j9]Jan Krajícek, Pavel Pudlák:
Quantified propositional calculi and fragments of bounded arithmetic. Math. Log. Q. 36(1): 29-46 (1990) - [c2]Jan Krajícek, Pavel Pudlák, Jirí Sgall:
Interactive Computations of Optimal Solutions. MFCS 1990: 48-60
1980 – 1989
- 1989
- [j8]Jan Krajícek, Pavel Pudlák:
On the structure of initial segments of models of arithmetic. Arch. Math. Log. 28(2): 91-98 (1989) - [j7]Jan Krajícek:
On the Number of Steps in Proofs. Ann. Pure Appl. Log. 41(2): 153-178 (1989) - [j6]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) - [c1]Jan Krajícek, Pavel Pudlák:
Propositional Provability and Models of Weak Arithmetic. CSL 1989: 193-210 - 1988
- [j5]Jan Krajícek, Pavel Pudlák:
The number of proof lines and the size of proofs in first order logic. Arch. Math. Log. 27(1): 69-84 (1988) - [j4]Jan Krajícek:
Some Results and Problems in The Modal Set Theory MST. Math. Log. Q. 34(2): 123-134 (1988) - 1987
- [j3]Jan Krajícek:
A note on proofs of falsehood. Arch. Math. Log. 26(1): 169-176 (1987) - [j2]Jan Krajícek:
A Possible Modal Formulation of Comprehension Scheme. Math. Log. Q. 33(5): 461-480 (1987) - 1985
- [j1]Jan Krajícek:
Some Theorems on the Lattice of Local Interpretability Types. Math. Log. Q. 31(29-30): 449-460 (1985)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-06-10 21:26 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
