I. (3 weeks) Mini-tutorial on complexity theory.

What is efficient computation.
P, NP, coNP, NP-completeness, Cook's theorem.
Important NP complete problems: SAT, solvability of polynomial identities, integer linear programming.
Randomized complexity classes RP, BPP
Hardness of approximation and the PCP theorem.
    Definitions, Important NP-hard approximation problems
    (MaxSAT, MaxCut, Vertex Cover, Sparsest Cut.) Review of state-of-the-art approximation algs and hardness results for these problem
    Khot's Unique games Conjecture, and implications.
Proof Complexity basics
    What is a propositional Proof system, and how it is connected to P versus NP question
    How standard algorithms and approximation algorithms fit into the proof complexity framework
    Important Proof systems that we will consider
    Resolution, Algebraic proof systems, Matrix Cut
    Proof systems
Overview of lower bounds and algorithmic implications

II. (2-3 weeks) Using Grobner bases to solve SAT.

Proof systems based on Hilbert's Nullstellensatz/Grobner bases.
Positive results: Grobner bases algorithms for SAT
Negative results: degree and size lower bounds
Open problems

III. (6-7 weeks) Linear Program Semi-Definite Programs algorithmic approaches

What are linear programs? How do we solve Linear Programs? We will present the simplex, ellipsoid and interior points methods.
What are semidefinite programs? solving them using ellipsoid and interior point methods.
Proof systems based on linear programming, and semidefinite programming: Lovasz Schrijver, Cutting Planes.

Using this toolbox for dealing with NP-hardness. Approximating "basic" problems. MaxCut algorithms and Sparsest cut Algorithms as prime examples. Using Linear and Semi-Definite programs to approximate MaxSAT.
The interplay between the analysis of such algorithms with combinatorial/geometrical/ probabilistic notions like concentration-of-measure, isoperimetric inequalities, expanding conditions.
Negative results: integrality gaps, LS-based integrality gaps

IV. Open problems