Laboratory of Structural Methods of Data Analysis in Predictive
Modeling Moscow Institute of Physics and Technology
ENG
Логин:
Пароль:

Лекция 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.

Bibliography:
(main)
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.

(supplementary:)
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.http://www.nada.kth.se/~viggo/wwwcompendium/.
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
 

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

03.05.2014

Exam.

02.05.2014

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).

30.04.2014

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

28.04.2014

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

26.04.2014

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

24.04.2014

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

22.04.2014

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

20.04.2014

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

18.04.2014

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