CSCI-GA.3033-106            Spring 2024

CS Dept,   New York University

Special Topics: Geometric Methods in Algorithm Design

Subhash Khot


General Information and Announcements

   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. 


Course Summary


Administrative Information

Lectures: Tue 10:15-12:15 (CIWW 202)

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