LAAW04 
10th April 2006
10:00 to 11:00 
P Pudlak 
$On \forall\Sigma_1^b$ sentences provable in bounded arithmetic 

LAAW04 
10th April 2006
11:30 to 12:00 
P Nguyen 
The complexity of proving the discrete Jordan Curve theorem and related principles 

LAAW04 
10th April 2006
12:00 to 12:30 
A Beckmann 
Uniform proof complexity 

LAAW04 
10th April 2006
14:00 to 15:00 
N Thapen 
$T^1_2, T^2_2$ and search problems 

LAAW04 
10th April 2006
15:30 to 16:00 
E Jerabek 
Approximate counting in bounded arithmetic 

LAAW04 
10th April 2006
16:00 to 16:30 
C Pollett 
When can $S^1_2$ prove the weak pigeonhole principle? 

LAAW04 
11th April 2006
09:30 to 10:30 
S Cook 
Capturing complexity classes by their reasoning power 

LAAW04 
11th April 2006
10:30 to 11:00 
M Vardi 
Constraint propagation as a proof system 

LAAW04 
11th April 2006
11:30 to 12:00 
M Soltys 
The proof complexity of matrix algebra 

LAAW04 
11th April 2006
12:00 to 12:30 
S Perron 
A minimal quantified proof system for polytime reasoning 

LAAW04 
11th April 2006
14:00 to 15:00 
R Impagliazzo 
Which SAT instances are the hardest? 

LAAW04 
11th April 2006
15:30 to 16:00 
S Riis 
Sporadic propositional proofs 

LAAW04 
11th April 2006
16:00 to 16:30 
N Galesi 
Resolution by pebbling games 

LAAW04 
12th April 2006
09:30 to 10:30 
T Pitassi 
Using lower bounds in proof complexity 

LAAW04 
12th April 2006
10:30 to 11:00 
J Nordstrom 
Narrow proofs may be spacious: separating space and width in resolution 

LAAW04 
12th April 2006
11:30 to 12:30 
N Segerlind 
Connections between zeroone programming, communication complexity and proof complexity 

LAAW04 
13th April 2006
09:30 to 10:30 
I Tzameret 
The strength of multilinear proofs 

LAAW04 
13th April 2006
10:00 to 10:30 
ML Bonet 
A complete resolutionlike calculus for Maxsat 

LAAW04 
13th April 2006
11:30 to 12:30 
S Dantchev 
Parametrised proof complexity 

LAAW04 
13th April 2006
14:00 to 14:30 
P Naumov 
Meta complexity of propositional proofs 

LAAW04 
13th April 2006
14:30 to 15:30 
M Alekhnovich 
On the power of LovaszSchrijver hierarchy 
