Reading group

We were reading Jan Krajíček's intriguing book Forcing with random variables and proof complexity.

Participants: Allan Borodin, Jeff Edmonds, Yuval Filmus, Kaveh Ghasemloo , Josh Grochow , Sebastian Müller, Jan Pachl, Toni Pitassi, Alasdair Urquhart.

Meetings

Date	Speaker	Subject
30 May 2013	Alasdair	Non-standard models of arithmetic (Appendix)
6 June 2013	Alasdair	The structures K(F) (§1)
13 June 2013	Yuval	Two-sorted structres, M_n, L_n (§5) The structure K(F_rud,G_rud) (§7) Obtaining lower bounds on lengths of proofs (§6,17,18,19)
20 June 2013	Yuval	The structures K(F_tree,G_tree) (§10.2), K(F_alg,G_alg) (§14.1,14.2), K(F⁰_PHP,G⁰_PHP) (§20.1) and K(F_PHP,G_PHP) (§21.2) Failure of PHP in K(F⁰_PHP,G⁰_PHP) (§20.3) Open induction and open comprehension in K(F_rud,G_rud) (§8.2,8.3) Quantifier elimination (§9) Quantifier elimination in K(F_tree,G_tree) (§11.1) Quantifier elimination in K(F_alg,G_alg) (§15.1)
27 June 2013	Toni	Håstad and pigeonhole principle switching lemmas (Beame, Fu & Urquhart)
4 July 2013	Toni	Classical pigeonhole principle lower bounds (Fu & Urquhart)
11 July 2013	Sebastian	Witnessing and preservation results for K(F_tree,G_tree), with implications: unprovability results and circuit lower bounds (§12) Differences between K(F_tree,G_tree) and K(F_PHP,G_PHP) (§22.5)
18 July 2013	Sebastian	Proving the existence of Skolem functions in K(F_tree,G_tree) and K(F_PHP,G_PHP) with an emphasis on their differences (§11,§21) A brief survey of such results for K(F_alg,G_alg)(§14–§16) Onwards to a potential lower bound for circuits with parity gates (§22)
25 July 2013	Sebastian	Continuation of last week with an emphasis on algebraic trees
1 August 2013	Break	We have a break
8 August 2013	Sebastian	Discussion about problems and possible solutions to the problems arising when trying to construct algebraic PHP models
15 August 2013	Break	We have a break
22 August 2013	Sebastian	Proof complexity generators (§29)
29 August 2013	Yuval	Conditional independence results (§24.1–3)

Supporting material

The book

Papers

The complexity of the pigeonhole principle, Miklós Ajtai.
A switching lemma primer, Paul Beame.
Simplified lower bounds for propositional proofs, Xudong Fu and Alasdair Urquhart.
On small size approximation models, Sasha Razborov.
On the method of approximation, Sasha Razborov.
On small size approximation models, Sasha Razborov.
Razborov's method of approximation, exposition by Tim Gowers.
Real Advantage, Sasha Razborov and Emanuele Viola.
On methods for proving lower bounds in propositional logic, Jan Krajicek.
On Frege and Extended Frege proof systems, Jan Krajicek.
Lower Bounds for Bounded Depth Frege Proofs via Buss-Pudlak Games, Eli Ben-Sasson and Prahladh Harsha.

Lecture notes

Some lecture notes by Yuval.
An overview of the different tree models.
Rough lecture notes on §24 by Yuval.