Krajíček Jan

Prof., RNDr., DrSc.
Born June 18, 1960 in Prague

• Member of Learned Society since 2004

Educational and professional preparation

• 1985, RNDr., Charles University;
• 1990, CSc., Czechoslovak Academy of Sciences;
• 1993, DrSc., AS CR;
• 2002, Associate Professor, CU;
• 2004, Professor of Mathematical Logic, CU;

Employment and academic positions

• 1985-present, Academy of Sciences;
• 2000-present, Charles University;
• 1988-89, 1990-91, visiting professor, University of Illinois (Urbana-Champaign);
• 1993, visiting professor (six months), University of Toronto;
• 1997-99, visiting scholar, Oxford University;
• 2004 (Spring term), member, Institute for Advanced Study, Princeton.
• 2006 and 2012 (Spring terms), senior visiting fellow, Isaac Newton Institute, Cambridge.

Membership and positions in international organizations and societies

• Association for Symbolic Logic Concilium (1999-2001 Council, 2002-2005 Committee on Logic in Europe, 2006-present Committe on Prizes and Awards)
• Member, American Mathematical Society
• 2009-present, Panel Member for the ERC Advanced Grant evaluation
• Member, editorial boards, Annals of Pure and Applied Logic, Notre Dame Journal of Formal Logic, Archive for Mathematical Logic, and Mathematical Methods in Computer Science
• over the years, member of program/organization committees of over 30 international conferences

Notable awards

• 1994, Award, young scientific workers, AS CR
• 1998, Award, Minister of Education, Youth and Sports (for Science)
• 2010, Award of the Academy of Sciences of the Czech Republic

Selected publications

• J. Krajíček: On the Number of Steps in Proofs. Annals of Pure and Applied Logic 41(2), 153-178, (1989)
• J. Krajíček, P. Pudlák and G. Takeuti: Bounded Arithmetic and the Polyno-mial Hierarchy, Annals of Pure and Applied Logic 52, 143-153, (1991).
• J. Krajíček: Fragments of Bounded Arithmetic and Bounded Query Classes, Transactions of the AMS 338(2), 587-598, (1993).
• J. Krajíček: Lower Bounds to the Size of Constant-Depth Propositional Proofs. J. of Symbolic Logic 59(1), 73-86, (1994).
• J. Krajíček, P. Pudlák and A. Woods: An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole principle. Random Structures and Algorithms 7(1), 15-39,(1995).
• P. Beame, R. Impagliazzo, J. Krajíček, T. Pitassi and P. Pudlák: Lower bounds on Hilbert.s Nullstellensatz and propositional proofs. Proceedings of the London Mathematical Society 73(3), 1-26, (1996).
• J. Krajíček: Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. J. of Symbolic Logic, 62(2), 457-486, (1997).
• J. Krajíček a P. Pudlák: Some consequences of cryptographical conjectures for S12 and EF. Information and Computation 140 (1), 82-94, (1998).
• J. Krajíček: Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds, J. of Symbolic Logic, 69(1), 265-286, (2004).
• J. Krajíček: An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams, J. of Symbolic Logic, 73(1), 227-237, (2008).
• J. Krajíček: Bounded arithmetic, propositional logic, and complexity theory, Cambridge University Press, 1995.
• J. Krajíček: Forcing with random variables and proof complexity, Cambridge University Press, 2011.

reference to the website »