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.