logo

Workshop on Circuit and Proof Complexity

1-7 October 2001, Edinburgh

Home | Scientific Programme & Participants | Workshop Arrangements | Registration Form | Timetable

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

Wednesday 3 October

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
Back to ICMS Website