Proof Complexity speakers and lectures
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.