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 |