## Proof Complexity speakers and lectures

## at the Fall school in Trest (Sept.'07)

## Lectures:

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.