
THEMATIC PROGRAMS 

April 24, 2014  
Thematic Program on the Foundations of Computational Mathematics

Course on Methodologies to deal
with intractability  Tuesdays
35 pm, Fields Institute, Stewart Library
Instructors: Avner
Magen and Toniann
Pitassi
Course on Computability and
Complexity in Geometry, Topology, and Dynamics Monday
and Wednesday 1011: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) Minitutorial on complexity theory.
What is efficient computation.
P, NP, coNP, NPcompleteness, 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 NPhard approximation problems
(MaxSAT, MaxCut, Vertex Cover, Sparsest Cut.) Review of stateoftheart 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. (23 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. (67 weeks) Linear Program SemiDefinite 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 NPhardness. Approximating "basic" problems. MaxCut algorithms and Sparsest cut Algorithms as prime examples. Using Linear and SemiDefinite programs to approximate MaxSAT.
The interplay between the analysis of such algorithms with combinatorial/geometrical/ probabilistic notions like concentrationofmeasure, isoperimetric inequalities, expanding conditions.
Negative results: integrality gaps, LSbased integrality gaps
IV. Open problems
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, noncomputability in topology, applications of noncomputability 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 noncomputable 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
Lecture 1 notes

Lecture 6 notes

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) NPComplete 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 Illposedness
9) Condition and the distance to illposedness
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.