|
|
CSCI-GA.3033-106
Spring 2025
CS Dept, New
York University
Special Topics: Geometric Methods
in Algorithm Design
Subhash Khot
|
You need to read one paper from this list and write a short report:
· N. Alon, M. Krivelevich, B. Sudakov, Finding a large hidden clique in a random graph.
· The influence of variables on Boolean functions, J. Kahn, G. Kalai and N. Linial.
You can add this paper too: E. Friedgut, G. Kalai, Every monotone property has a sharp threshold.
· A. Gupta, Embedding tree metrics into low dimensional Euclidean spaces.
· A tight bound on approximating arbitrary metrics by tree metrics, J. Fakcharoenphol, S. Rao, K. Talwar.
· Approximation Algorithms for Unique Games, Luca Trevisan.
· G. Schoenebeck, Linear Level Lasserre Lower Bounds for Certain k-CSPs.
· N. Bansal, Constructive Algorithms for Discrepancy Minimization.
· Any paper from here (as long as the material is not covered in class).
· Uriel Feige. Approximating the bandwidth via volume respecting embeddings.
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.
The LLL algorithm: easier expositions might be available in books, surveys, or course notes.
· Twice-Ramanujan Sparsifiers (J. Batson, D. Spielman, N. Srivastava), STOC 2009.
Available
at: http://arxiv.org/abs/0808.0163
Papers that are not necessarily related to topics of the course, but you could still choose to read from these:
· 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
· 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
· 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