G22.3033-005            Spring 2011

CS Dept,   New York University

Special Topics in Algorithms

Subhash Khot

General Information and Announcements

   Recommended reading (the list is biased towards the results that I am more familiar with):

·         Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, Primes is in P, in Annals of Mathematics, vol. 160, no. 2, pp. 781-793, 2004

Available at:  http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

·         O. Reingold, Undirected ST-Connectivity in Log-Space, STOC 2005.

Available at:   http://www.wisdom.weizmann.ac.il/~reingold/publications/index.html

·         Twice-Ramanujan Sparsifiers (J. Batson, D. Spielman, N. Srivastava), STOC 2009.

Available at:   http://arxiv.org/abs/0808.0163

·         Decoding of Reed-Solomon codes beyond the error-correction bound  (M. Sudan)

Available at:  http://people.csail.mit.edu/madhu/papers/1996/reeds-journ.pdf

·         N. Alon, Y. Matias and M. Szegedy, The space complexity of approximating the frequency moments, J. Comp. Sys. Sci. 58 (1999), 137-147.

Available at:   http://www.tau.ac.il/~nogaa/PDFS/amsz4.pdf

·         A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries.  M. Jerrum, A. Sinclair, and E. Vigoda.  In Journal of the ACM, 51(4):671-697, 2004.

Available at:   http://www.cc.gatech.edu/~vigoda/Permanent.pdf

·         Uriel Feige. Approximating the bandwidth via volume respecting embeddings. Journal of Computer and System Sciences, 60(3), 510--539, June 2000.

Available at:  http://www.wisdom.weizmann.ac.il/~feige/approx.html

·         Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. (1982). "Factoring polynomials with rational coefficients". Mathematische Annalen 261 (4): 515–534.

Available at:    https://openaccess.leidenuniv.nl/dspace/bitstream/1887/3810/1/346_050.pdf

The LLL algorithm:  easier expositions might be available in books, surveys, or course notes.  

·         Algorithms for quantum computation: Discrete logarithms and factoring (P. Shor).

Available at:  http://www-math.mit.edu/~shor/elecpubs.html

Easier expositions might be available in books, surveys, or course notes.  

Course Summary

Administrative Information

Lectures: Wed 7:10-9:00 (WWH 312)

Professor: Subhash Khot – Off 416,  Ph:  212-998-4859

Course Syllabus

This is a special topics course with a focus on advanced algorithms.


For many NP-hard problems, one can efficiently compute approximate solutions with a

non-trivial guarantee on the approximation ratio. Starting with the seminal work of

Goemans and Williamson in early 90s, several approximation algorithms have been designed

based on a semi-definite programming relaxation followed by a rounding scheme. This course

will cover many of these SDP-based algortihms along with other applications of SDPs in

computer science.


Tentatively, the topics include:

* Brief overview of SDPs. www-math.mit.edu/~goemans/PAPERS/icm98.ps

* MAX-CUT: http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf

* Graph coloring: http://people.csail.mit.edu/madhu/papers/1994/kms-journ.pdf

* Sparsest Cut: http://www.cs.princeton.edu/~arora/pubs/arvfull.pdf

* Unique Games:




* Discrepancy minimization: http://arxiv.org/abs/1002.2259

* SDPs, integrality gaps, PCPs, and inapproximability: