Suggested Papers

  • Expander flows, geometric embeddings and graph partitioning (Sanjeev Arora, Satish Rao, Umesh Vazirani - JACM)

         (See also the Lecture Notes of Thomas Rothvoss on ARV - arXiv)
  • Euclidean distortion and the sparsest cut (Sanjeev Arora, James R. Lee, Assaf Naor - arXiv)

  • Some optimal inapproximability results (Johan Hastad - JACM)

  • The PCP theorem by gap amplification (Irit Dinur - JACM)
  • An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem (Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi - SODA 10)
  • Similarity estimation techniques from rounding algorithms (Moses Charikar - STOC 02)
  • The Complexity of Computing a Nash Equilibrium (Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou - SIAM J. Comput.)
  • An average-case depth hierarchy theorem for Boolean circuits (Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan - arXiv)
  • Spectral Approaches to Nearest Neighbor Search (Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer - arXiv)
  • Approximation Resistance from Pairwise Independent Subgroups (Siu On Chan - ECCC)
  • Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds (Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf - STOC 12)
  • ETH Hardness for Densest-k-Subgraph with Perfect Completeness (Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein - arXiv)