# Seminars (LAAW04)

Videos and presentation materials from other INI events are also available.

Search seminar archive

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