The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Newton InstituteWeb SeminarsProgrammes & Workshops2006LAA > LAAw04

10 - 13 Apr 2006

LAAw04 - New Directions in Proof Complexity

in association with the LAA programme

Warning: Information on this page may be out of date.

For the full list of seminars given during this programme, see:

13 Apr 2006: Parametrised proof complexity
S. Dantchev
13 Apr 2006: A complete resolution-like calculus for Maxsat
M.L. Bonet
13 Apr 2006: The strength of multilinear proofs
I. Tzameret
12 Apr 2006: Connections between zero-one programming, communication complexity and proof complexity
N. Segerlind
12 Apr 2006: Narrow proofs may be spacious: separating space and width in resolution
J. Nordstrom
12 Apr 2006: Using lower bounds in proof complexity
T. Pitassi
11 Apr 2006: Resolution by pebbling games
N. Galesi
11 Apr 2006: Sporadic propositional proofs
S. Riis
11 Apr 2006: Which SAT instances are the hardest?
R. Impagliazzo
11 Apr 2006: A minimal quantified proof system for polytime reasoning
S. Perron
11 Apr 2006: The proof complexity of matrix algebra
M. Soltys
11 Apr 2006: Capturing complexity classes by their reasoning power
S. Cook
11 Apr 2006: Constraint propagation as a proof system
M. Vardi
10 Apr 2006: When can $S^1_2$ prove the weak pigeonhole principle?
C. Pollett
10 Apr 2006: Approximate counting in bounded arithmetic
E. Jerabek
10 Apr 2006: $T^1_2, T^2_2$ and search problems
N. Thapen
10 Apr 2006: Uniform proof complexity
A. Beckmann
10 Apr 2006: The complexity of proving the discrete Jordan Curve theorem and related principles
P. Nguyen
10 Apr 2006: On $\forall\Sigma_1^b$ sentences provable in bounded arithmetic
P. Pudlak

Newton InstituteWeb SeminarsProgrammes & Workshops2006LAA > LAAw04

Comments or suggestions? Send feedback!