Workshop on Circuit and Proof Complexity
1-7 October 2001, Edinburgh
Timetable
This timetable is subject to change. Please check this page to be sure you are using the most up to date version.25 September 2001
Monday | Tuesday | Wednesday | Thursday | Friday
| Monday 1 October | |
| 0930 – 1030 | ICMS open for Registration |
| 1030 – 1100 | Tea/coffee break |
| 1100 – 1200 | Pavel Pudlak On the complexity of propositional intuitionistic proofs |
| 1200 – 1400 | Lunch break |
| 1400 – 1500 | Stefan Dantchev Tree resolution proofs of the weak pigeon-hole principle |
| 1500 – 1530 | Tea/coffee break |
| 1530 - 1630 | Nicola Galesi
tba |
| 1700 – 1830 | Informal reception at ICMS |
Monday | Tuesday | Wednesday | Thursday | Friday
| Tuesday 2 October | |
| 0930 – 1030 | Ran Raz On the complexity of matrix product |
| 1030 – 1100 |
Tea/coffee break |
| 1100 – 1200 | Alan Woods A lower bound on prime testing |
| 1200 – 1400 | Lunch break |
| 1400 – 1500 | Jan Krajicek
Approximate counting, dimension and weak pigeonhole principle |
| 1500 – 1530 | Tea/coffee break |
| 1530 – 1630 | Neil Thapen Structures definable in models of bounded arithmetic |
| 1630 – 1700 | Tsuyoshi Morioka Relative complexity of search problems and unprovability of some combinatorial principles in relativized T^1_2 |
Monday | Tuesday | Wednesday | Thursday | Friday
| 0930 – 1030 | Stephen Cook A survey of complexity classes and their associated propositional proof systems and theories |
| 1030 – 1100 | Tea/coffee break |
| 1100 – 1200 | Nathan Segerlind Counting gates are stronger than counting axioms |
| 1200 – 1400 | Lunch break |
| 1400 – 1700 | Free afternoon (Tea/coffee served at 1500) |
Monday | Tuesday | Wednesday | Thursday | Friday
| Thursday 4 October | |
| 0930 – 1030 | Gaisi Takeuti S^1_2 versus V^1_2 and R^1_2 versus U^1_2 |
| 1030 – 1100 | Tea/coffee break |
| 1100 – 1200 | Michail Alekhnovich
An exponential separation between regular and general resolution (joint with J.Johannsen, T.Pitassi and A.Urquhart) |
| 1200 – 1400 | Lunch break |
| 1400 – 1500 | Arnold Beckmann
Remarks on dynamic ordinals |
| 1500 – 1530 | Tea/coffee break |
| 1530 – 1600 | Albert Atserias
Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms |
| 1900 | Optional conference dinner |
Monday | Tuesday | Wednesday | Thursday | Friday
| Friday 5 October | |
| 0930 – 1030 | Samuel Buss (provisional)
Tba |
| 1030 – 1100 |
Tea/coffee break |
| 1100 – 1200 | Paul Beame A sharp threshold in proof complexity |
| 1200 – 1400 | Lunch break |
| 1400 – 1500 | Eli Ben-Sasson Lower bounds for Tseitin contradictions in bounded depth Frege |
| 1500 – 1530 | Tea/coffee break, Close of meeting |
Monday | Tuesday | Wednesday | Thursday | Friday