Computational Geometry organized by Jiri Matousek
Computational geometry studies efficient algorithms for computing with geometric objects, especially in low-dimensional spaces. There is also a close connection to discrete geometry, since the analysis of many algorithms relies on understanding the combinatorial complexity of geometric configurations. The speakers are active researchers in the field and they will address several recent developments.
Confirmed speakers: Takeshi Tokuyama (Tohoku University), Anastasios Sidiropoulos (University of Toronto), Xavier Goaoc (INRIA Lorraine), Christian Knauer (Freie Universitat Berlin)
Proof Complexity organized by Jan Krajicek
Proof complexity studies the informal concept of a feasible proof. The complexity of a proof is measured by its size; this is essentially equivalent to the non-deterministic time.
In propositional logic the main question is whether there exists a proof system in which every propositional tautology has a short proof, a proof of size bounded by a polynomial in the size of the formula. With the general Cook-Reckhow definition of proof systems the question is equivalent to the problem whether the computational complexity class NP is closed under complementation.
Strong lower bounds are known for many classes of particular proof systems. These lower bounds imply that corresponding classes of algorithms for SAT or automated theorem proving need exponential time. Proof complexity has many other facets and the speakers will address some of them.
Confirmed speakers: Olaf Beyersdorff (Leibniz University Hannover), Stefan Dantchev (Durham University), Edward A. Hirsch (Steklov Institute of Mathematics at St.Petersburg), Sebastian Muller (Charles University in Prague), Iddo Tzameret (Academy of Sciences, Prague).