THEMATIC PROGRAMS

• Course on Methodologies to deal with intractability - Tuesdays 3-5 pm, Fields Institute, Stewart Library
  Instructors: Avner Magen and Toniann Pitassi
  

• Course on Computability and Complexity in Geometry, Topology, and Dynamics Monday and Wednesday 10-11:30 a.m.
  Instructors: Alex Nabutovsky and Michael Yampolsky

Course on Methodologies to Deal with Intractability
(Tuesdays 3-5 pm)
Course link

Instructors: Avner Magen and Toniann Pitassi

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

Course on Computability and Complexity in Geometry, Topology, and Dynamics
Instructors: Alex Nabutovsky and Michael Yampolsky
(Monday and Wednesday 10-11:30 a.m)

Part I: Computability and Complexity in Topology and Differential Geometry
(A. Nabutovsky)

Computability (Turing machines, recursive functions, degrees of unsolvability), algorithmic information theory, unsolvable problems in group theory, group homology, non-computability in topology, applications of non-computability and algorithmic information theory in geometric calculus of variations (``thick" knots, local minima of Riemannian functionals, geometry of moduli spaces arising in differential geometry).

Literature: S. Weinberger, ``Computers, Rigidity and Moduli", Princeton
University Press, 2005 and papers of the instructor.

Part II: Computability and Complexity in Dynamics (M. Yampolsky)

Basic notions of computable analysis: computable real functions, computable sets in R^n. Dynamics of rational maps of the Riemann sphere: Fatou and Julia sets. Computability and complexity of Julia sets. Algorithms used to draw Julia sets versus theoretical complexity bounds. Constructing non-computable examples of Julia sets. Computability of filled Julia sets of polynomials. Computable properties and the topology of Julia sets. Open problems.

Literature: M. Braverman, M. Yampolsky, "Computability of Julia sets", Springer, 2008

Complexity and Accuracy in Numeric Computations
(Tuesdays 10-12 pm)

Instructors: Lenore Blum and Felipe Cucker

Note: There will be no lectures on Oct. 20 and Oct. 27

1) Computing over a ring or field (especially over the reals or complex numbers): a machine model.
2) Measuring Complexity and the classes P and NP over a ring or field
3) NP-Complete Problems (universal and specific)
4) Algebraic setting for the problem "P=NP?"
5) Lower bounds and other complexity classes
6) Measuring accuracy
7) Error analysis and Condition numbers
8) Poor conditioning and Ill-posedness
9) Condition and the distance to ill-posedness
10) Condition of random data

Taking the Institute's Courses for Credit
As graduate students at any of the Institute's University Partners, you may discuss the possibility of obtaining a credit for one or more courses in this lecture series with your home university graduate officer and the course instructor. Assigned reading and related projects may be arranged for the benefit of students requiring these courses for credit.

BACK TO TOP