Skip to content

Workshop Programme

for period 10-13 April

New Directions in Proof Complexity

10-13 April

Timetable

Monday 10 April
08:30-10:00 Registration LAA
10:00-11:00 Pudlak, P (Academy of Sciences, Prague) LAA
  $On \forall\Sigma_1^b$ sentences provable in bounded arithmetic Sem 1
11:00-11:30 Coffee LAA
11:30-12:00 Nguyen, P (Toronto) LAA
  The complexity of proving the discrete Jordan Curve theorem and related principles Sem 1
12:00-12:30 Beckmann, A (Wales) LAA
  Uniform proof complexity Sem 1
12:30-13:30 Lunch at Wolfson Court LAA
14:00-15:00 Thapen, N (Academy of Sciences, Prague) LAA
  $T^1_2, T^2_2$ and search problems Sem 1
15:00-15:30 Tea LAA
15:30-16:00 Jerabek, E (Toronto) LAA
  Approximate counting in bounded arithmetic Sem 1
16:00-16:30 Pollett, C (San Jose State University) LAA
  When can $S^1_2$ prove the weak pigeonhole principle? Sem 1
17:00-18:00 Wine and Beer Reception LAA
18:45-19:30 Dinner at Wolfson Court (Residents only) LAA
Tuesday 11 April
09:30-10:30 Cook, S (Toronto) LAA
  Capturing complexity classes by their reasoning power Sem 1
10:30-11:00 Vardi, M (Rice ) LAA
  Constraint propagation as a proof system Sem 1
11:00-11:30 Coffee LAA
11:30-12:00 Soltys, M (McMaster) LAA
  The proof complexity of matrix algebra Sem 1
12:00-12:30 Perron, S (Toronto) LAA
  A minimal quantified proof system for polytime reasoning Sem 1
12:30-13:30 Lunch at Wolfson Court LAA
14:00-15:00 Impagliazzo, R (California, San Diego) LAA
  Which SAT instances are the hardest? Sem 1
15:00-15:30 Tea LAA
15:30-16:00 Riis, S (London) LAA
  Sporadic propositional proofs Sem 1
16:00-16:30 Galesi, N (Rome) LAA
  Resolution by pebbling games Sem 1
18:45-19:30 Dinner at Wolfson Court (Residents only) LAA
Wednesday 12 April
09:30-10:30 Pitassi, T (Toronto) LAA
  Using lower bounds in proof complexity Sem 1
10:30-11:00 Nordstrom, J (Royal Institute of Technology, Stockholm) LAA
  Narrow proofs may be spacious: separating space and width in resolution Sem 1
11:00-11:30 Coffee LAA
11:30-12:30 Segerlind, N (Washington) LAA
  Connections between zero-one programming, communication complexity and proof complexity Sem 1
12:30-13:30 Lunch at Wolfson Court LAA
19:30-18:00 Conference Dinner at Christ's College (Dining Hall) LAA
Thursday 13 April
09:30-10:30 Tzameret, I (Tel Aviv) LAA
  The strength of multilinear proofs Sem 1
10:00-10:30 Bonet, ML (Barcelona) LAA
  A complete resolution-like calculus for Maxsat Sem 1
11:00-11:30 Coffee LAA
11:30-12:30 Dantchev, S (Durham) LAA
  Parametrised proof complexity Sem 1
12:30-13:30 Lunch at Wolson Court LAA
14:00-14:30 Naumov, P (McDaniel College) LAA
  Meta complexity of propositional proofs Sem 1
14:30-15:30 Alekhnovich, M (California, San Diego) LAA
  On the power of Lovasz-Schrijver hierarchy Sem 1
15:30-16:00 Tea LAA
18:45-19:30 Dinner at Wolfson Court (Residents only) LAA
Other Seminars
Seminars in the University
National and International Scientific Research Meetings

Back to top ∧