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:

·         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:


 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:

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

Available at:

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

Available at:

·         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:

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

Available at:

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.


* Graph coloring:

* Sparsest Cut:

* Unique Games:

* Discrepancy minimization:

* SDPs, integrality gaps, PCPs, and inapproximability: