|September 21, 2014|
Thematic Program on the Foundations of Computational Mathematics
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
All courses will be held at the Fields Institute, Room 230
unless otherwise noted.
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
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
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
Part I: Computability and Complexity in Topology and Differential Geometry
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
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.