Jindřich Zapletal

Grants
- South Eastern Logic Symposium (NSF DMS- 362273)
  from 01/01/2015 to 01/01/2018 investigator
- A grant to organize an annual weekend conference at University of Florida on the connections between set theory and computability.
- Feasibility, Logic and Randomness in computational complexity (FEALORA(339691))
  from 01/01/2014 to 31/12/2018 investigator
- Programme type: FP7 ERC Advanced Grant Objectives: This project aims at making progress in the study of basic open problems in computational complexity, such as the P versus NP problem. There are several approaches to these difficult problems, one of which is proof complexity. In proof complexity we not only study the lengths of proofs in various proof systems, but also first order theories associated with complexity classes, collectively called bounded arithmetic. Proving separations between proof systems or theories in bounded arithmetic, however, seems as difficult as separating the corresponding complexity classes. Our group has been working in proof complexity for more than two decades and has played an important role in the development of the field. The novelty of this project is its focus on the role of the following two concepts in proof complexity: incompleteness and pseudorandomness. The incompleteness phenomenon is well understood in the context of stronger arithmetical theories, but little is known in bounded arithmetic. As it may be extremely difficult to solve the problems about incompleteness in the polynomial time domain, one of the approaches we will try is proposing axioms that will decide these questions. Similarly, pseudorandomness has been intensively researched in computational complexity, but its role in proof complexity still needs more research.
- Ideals and Equivalence Relations (NSF DMS 1161078)
  from 10/10/2012 to 10/10/2015 investigator
- Set theory and its applications (MEB051006)
  from 01/01/2010 to 31/12/2011 main investigator
- Programme type: MOBILITY - Polsko Objectives: Cooperation in the subject of descriptive set theory and forcing. Finishing the book "Ideals and Equivalences", coothored by Jindřich Zapletal and Marcin Sabok. Organizing bilateral conferences in Prague and Hejnice on the subject of infinite games, set theory, and forcing. Lectures of Jindřich Zapletal at the Institute of Mathematics in Wroclaw.
- Mathematical logic, complexity, and algorithms (IAA100190902)
  from 01/01/2009 to 31/12/2013 investigator
- Project of basic research in mathematical logic and theoretical computer science. We focus on bounded arithmetic and proof complexity, set theory, computational complexity theory, and the theory of algorithms. The topics range from foundational areas of mathematics to algorithmic problems motivated by applied research. The results of the project will be published in high quality international scientific journals and in the proceedings of selective conferences.
- Set theory and its applications (MEB060909)
  from 01/01/2009 to 31/12/2010 main investigator
- Programme type: MOBILITY - Austria Objectives: Exploring the interaction between set theory on one hand, and abstract analysis and combinatorics on the the other.