COURSES

Lance Fortnow Northwestern University, Toyota Technological Institute: Structural Complexity		Nicola Galesi University of Rome "La Sapienza": Proof Complexity
Heribert Vollmer University of Hanover: Satisfiability Problems		Uri Zwick Tel Aviv University: Complexity of Graph Algorithms Based on Matrix Multiplication

---

• Structural Complexity
  Lance Fortnow
  
  We will look at the famous P vs. NP problem and how this question led to the rich development of computational complexity classes. Topics we plan to cover include: the polynomial-time hierarchy and counting complexity, alternation, probabilistic and non-uniform models, interactive and probabilistically checkable proof systems and a structural approach to quantum computing.
  
  

---

• Proof Complexity
  Nicola Galesi
  
  Proof complexity investigates how difficult is to prove family of tautologies in propositional proof systems. It plays for the study of feasible proofs the same role that circuit complexity plays for the study of feasible computations. Main problems and motivations in proof complexity are strictly related with problems in complexity theory like NP vs co-NP. In the tutorial we will give an introduction to the field of proof complexity. Then we will show some of the main techniques and results for studying the limits to the provability in one of the most studied proof systems: Resolution. We then will look at stronger proof systems motivating recent problems and results starting from what seen for Resolution.
  Presentation: Introduction to Circuit Complexity
  Presentation: Resolution
  Presentation: Exponential Lower Bounds for DAG-like Resolution
  Presentation: Other Measures and Methods for Resolution
  
  

---

• Satisfiability Problems
  Heribert Vollmer
  
  Going back to the famous theorem by Cook and Levin, satisfiability problems have turned out to be central in computational complexity theory. In this tutorial we will prove complexity classifications of satisfiability and related problems for propositional logic, modal logic, temporal logic, constraint satisfaction, default logic, etc. In each case we will identify tractable fragments of algorithmic problems that are intractable in the general case. We will develop a powerful toolbox to attack questions like these, making use of Post's lattice of all closed classes of Boolean functions.
  Presentation: Constraint Satisfaction
  Presentation: Default Logic
  Presentation: Linear Temporal Logic
  Classes
  
  

---

• Complexity of Graph Algorithms Based on Matrix Multiplication
  Uri Zwick
  
  We consider ways of harnessing the power of fast algebraic matrix multiplication algorithms to solve various graph algorithmic problems, such as (dynamic) reachability problems, shortest paths problems and matching problems.
  Presentation: pdf
  Presentation: pptx