Laboratory of Structural Methods of Data Analysis in Predictive
Modeling Moscow Institute of Physics and Technology

Лекция Brief Introduction to Modern Complexity Theory

Maximov Yury
Должность: Младший научный сотрудник

Описание курса

Independent University of Moscow

Moscow Institute of Physics and Technology

The main goal of this course is to acquaint the students with new results and ideas in complexity theory developed in the last 20 years.

1. Arora S., Barak B. Computational complexity: a modern approach. Cambridge University Press, 2012.
2. Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M. Complexity and Approximation. Combinatorial optimization problems and their approximability properties. Springer Verlag, 2012. 524 p.
3. Gärtner B., Matousek J. Approximation Algorithms and Semidefinite Programming. Berlin: Springer. 2012, 251p.

1. Khot S., Kindler G., Mossel E., O'Donnell R. Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs. SIAM J. Comput. 37(1): 319-357. 2007
2. Dinur I., Safra S. On the hardness of approximating minimum vertex cover. Annals of Mathematics. 162 (1): 439–485. 2005.
3. Håstad J. Some Optimal Inapproximability Results. Journal of the ACM (JACM). 48 (4): 798-859. 2001.
4. Trevisan L. On Khot’S unique games conjecture. Bulletin of the AMS. 49(1): 91–111. 2012
5. Makarychev K., Makarychev Y. How to Play Unique Games on Expanders. LNCS. 6534: 190-200. 2011.
6. Mossel E., Umans C.: On the complexity of approximating the VC dimension. J. Comput. Syst. Sci. 65(4): 660-671 (2002)

to Lecture 7
1. Umans C. Hardness of Approximating Minimization Problems. In Proc. 40th FOCS.
2. Umans С. The Minimum Equivalent DNF Problem and Shortest Implicants. J. Comput. Syst. Sci. 63(4): 597-611 (2001)
3. Dick C., Umans C. Improved inapproximability factors for some minimization problems. Electronic Colloquium on Computational Complexity (ECCC) 16: 107 (2009)

Compendiums of NP-hard problems
1. Crescenzi P., Kann V., Halldórsson M., Karpinski M., Woeginger G. A compendium of NP-optimization problems.
2. Schaefer M. and Umans C. Completeness in the Polynomial-Time Hierarchy: a compendium. SIGACT News. Guest Complexity Theory column. September 2002.
3. Schaefer M. and Umans C. Completeness in the Polynomial-Time Hierarchy: Part II. SIGACT News. Guest Complexity Theory column. December 2002.


Application areas: 
Data mining
Modeling and optimization of complex systems
Equilibrium flows in congested traffic systems

Research topics: 
Statistical methods
Structural optimization
Stochastic optimization and optimal stopping
Huge-scale problems

Даты проведения и расписание:
Дата Расписание




18-00 – 21-00.
Lecture 7*. Umans results on the second level problems. Shortest Implicant Problem. Min TT-DNF Problem (NP complete) vs. Min-Equivalent DNF Problem (Sigma_2^p complete).


18-00 – 20-30.
Lecture 6. Lower bounds in data analysis/optimization problems.


18-00 – 21-00.
Lecture 5. Unique Games Conjecture and Convex Optimization.


18-00 – 21-00.
Lecture 4. 3-bit test (Johan. H?stad). PCP based lower bounds for 3-Sat, Min-Vertex-Cover, Max-Cut.


18-00 – 20-30.
Lecture 3. Proof sketch of PCP theorem (part 2).


18-00 – 21-00.
Lecture 2. 3-Sat problem. Probabilistically checkable proof. Proof sketch of PCP theorem (part 1).


18-00 – 21-00.
Lecture 1. Polynomial hierarchy. Classes P and NP. Oracle calculus.


18-00 – 21-00.
Lecture 0. Basics of probability and descrete mathematics. Expanders, Cheeger inequality, Measure concentration phenomenon.