Proof Complexity speakers and lectures
at the Fall school in Trest (Sept.'07)
Emil Jerabek (Prague): "Approximate counting in bounded arithmetic"
Abstract: We will show how to formalize Sipser-style approximate counting by hash functions in bounded arithmetic using variants of the weak pigeonhole principle. We will also discuss some applications.
Jan Krajicek (Prague): "Proof systems with advice"
Phuong Nguyen (Toronto): "Bounded Arithmetic for Small Complexity Classes"
Jakob Nordstrom (Stockholm): "On length, width and space in resolution"
Neil Thapen (Prague): "Bounded arithmetic and propositional translations"
Iddo Tzameret (Tel Aviv): "Resolution over linear equations and multilinear proofs"
Abstract: We shall discuss extensions of resolution that operate with disjunctions of linear equations (instead of clauses); Concentrating on connections with multilinear proofs, which are algebraic proofs operating with multilinear arithmetic formulas (i.e., arithmetic formulas in which every gate computes a multilinear polynomial).
Joint work with Ran Raz.
There should be also time to discuss informally other topics in proof complexity mentioned in the original announcement.