Algorithms Reading Group

Moses Charikar

This is a weekly algorithms reading group.

Time: Tuesday, 3:30 pm
Location: CS 402

Mailing list for announcements:

• Subscribe to algo-seminar.

Schedule

• [Sep 26] Moses Charikar:
  Low distortion embeddings for edit distance, Rafail Ostrovsky, Yuval Rabani, STOC 2005.
• [Oct 3] Yury Makarychev:
  Nonembeddability theorems via Fourier analysis, Subhash Khot and Assaf Naor, FOCS 2005.
• [Oct 10] Jan Vondrak (in CS 401):
  On maximizing welfare when utility functions are subadditive, by Uriel Feige, STOC 2006.
• [Oct 17] Jan Vondrak:
  Approximation algorithms for allocation problems: Improving the factor of 1-1/e, by Uriel Feige and Jan Vondrak, FOCS 2006.

Suggestions for presentations

• Complexity of Equilibria
  • The Complexity of Computing a Nash Equilibrium, Constantinos Daskalakis, Paul W. Goldberg and Christos H. Papadimitriou, STOC 2006.
  • Settling the Complexity of 2-Player Nash-Equilibrium, Xi Chen and Xiaotie Deng, FOCS 2006
  • Computing Nash Equilibria: Approximation and Smoothed Complexity, Xi Chen, Xiaotie Deng and Shang-Hua Teng, FOCS 2006.
• Metric embeddings
  • Low distortion embeddings for edit distance, Rafail Ostrovsky, Yuval Rabani, STOC 2005.
  • Lower-Stretch Spanning Trees, M. Elkin, Y. Emek, D. Spielman, and S. Teng, STOC 2005.
  • Nonembeddability theorems via Fourier analysis, Subhash Khot and Assaf Naor, FOCS 2005.
  • Improved lower bounds for embeddings into L_1, Robert Krauthgamer and Yuval Rabani, SODA 2006.
• Hardness of learning problems
  • New Results for Learning Noisy Parities and Halfspaces, Vitaly Feldman and Parikshit Gopalan and Subhash Khot and Ashok Kumar Ponnuswami, FOCS 2006
  • Hardness of Learning Halfspaces with Noise, Venkatesan Guruswami and Prasad Raghavendra, FOCS 2006
  • Cryptographic Hardness Results for Learning Intersections of Halfspaces, Adam R. Klivans and Alexander A. Sherstov, FOCS 2006
• Compressed Sensing
  • See the Compresses Sensing Resources page for several references.
  • Decoding by Linear Programming, Emmanuel Candès and Terence Tao, IEEE Transactions on Information Theory, Vol. 51, No. 12, pp. 4203-4215, Dec. 2005.
  • Error Correction via Linear Programming. Emmanuel J. Candes and Mark Rudelson and Terence Tao and Roman Vershynin, FOCS 2005.
• Inclusion-Exclusion Algorithms for Counting
  • Inclusion-Exclusion Algorithms for Counting Set Partitions, Andreas Björklund and Thore Husfeldt, FOCS 2006.
  • An O(2^n) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion-Exclusion, Mikko Koivisto, FOCS 2006.
• Other interesting papers (deliberately excludes talks we will see at Princeton)
  • The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into L1, Subhash Khot and Nisheeth Vishnoi, FOCS 2005.
  • Integrality Gaps for Sparsest Cut and Minimum Linear Arrangement Problems, Nikhil Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi, STOC 2006.
  • On maximizing welfare when utility functions are subadditive, Uriel Feige, STOC 2006.
  • Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method, Roman Vershynin, FOCS 2006.
  • Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design Problems, Chandra Chekuri, MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour, FOCS 2006.
  • Worst-case and Smoothed Analyses of the ICP Algorithm, With an Application to the k-means Method, David Arthur, Sergei Vassilvitskii, FOCS 2006.
  • Local Graph Partitioning using PageRank Vectors, Reid Andersen, Fan Chung and Kevin Lang, FOCS 2006.