|
|
G22.3033-005
Spring 2011
CS Dept, New
York University
Special Topics in Algorithms
Subhash
Khot
|
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.
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:
http://ttic.uchicago.edu/~yury/papers/unique.pdf
http://www.cs.princeton.edu/~dsteurer/ugefinal.pdf
http://www.cs.princeton.edu/~dsteurer/subexpug.pdf
* Discrepancy minimization: http://arxiv.org/abs/1002.2259
* SDPs, integrality gaps, PCPs, and inapproximability:
http://www.cc.gatech.edu/fac/praghave/Files/extabstract.pdf
http://www.cs.nyu.edu/~khot/papers/gl-journal-ver1.pdf
References