München
PDMI TUM State University St. Petersburg
Steklov Institute St. Petersburg Technische Universität München State University St. Petersburg

Joint Advanced Student School (JASS)

Course 1:  Propositional Proof Complexity


St. Petersburg - Sunday, March 29 through Tuesday, April 7, 2009



Participants:


Stefan Kunkel

Introduction to the Theory of Complexity Classes and Logic
Michael Herrmann

Frege Systems
Maximilian Schlund

Polynomial Calculus
Mykola Protsenko

Width-based lower bounds for resolution
Alisa Knizel

Razborov’s theorem, interpolation method, and lower bounds for Resolution and Cutting Planes
Sergey Nurk

Lower bounds for k-DNF Resolution on random 3-CNFs
Alexander Glazman

Switching Lemma
Ivan Monakhov

Lower Bounds for Bounded Depth Frege
Tobias Lieber

Automatization and Non-Automatizability


Dmitry Antipov

Optimal proof systems and disjoint NP pairs


Paper
Slides
Markus Latte

Pseudorandom generators hard for propositional proof systems
Paper
Slides
Grigory Yaroslavtsev

Lower bounds using communication complexity
Paper
Slides
Dmitry Itsykson

Teaching Assistant
Dmitro Chibisov

Teaching Assistant
Prof. Dr. E. Hirsch

Course Director


Prof. Dr. Ernst W. Mayr

Course Director


    <-Back