• [Oct 10] Jan Vondrak (in CS 401):\\

• [Oct 10] Jan Vondrak:
  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.

• [Sep 26] Moses Charikar:\\

• [Oct 3] Yury Makarychev:
  Nonembeddability theorems via Fourier analysis, Subhash Khot and Assaf Naor, FOCS 2005.

• On maximizing welfare when utility functions are subadditive, Uriel Feige, STOC 2006.

• [Sep 26] Moses Charikar will present the paper:\\

• [Sep 26] Embedding edit distance into L_1
  Moses Charikar will present the paper:\\

This is a weekly algorithms reading group.

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

Schedule

• [Sep 26] Embedding edit distance into L_1
  • Moses Charikar will present the paper:
    Low distortion embeddings for edit distance, Rafail Ostrovsky, Yuval Rabani, STOC 2005.

• Subscribe to algo-seminar.

• Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design Problems, Chandra Chekuri, MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour, FOCS 2006.

• Integrality Gaps for Sparsest Cut and Minimum Linear Arrangement Problems, Nikhil Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi, STOC 2006.

• Improved lower bounds for embeddings into L_1, Robert Krauthgamer and Yuval Rabani, SODA 2006.

• [[http://www.cs.berkeley.edu/~robi/papers/KR-EmbedLB-SODA06.pdf|Improved lower bounds for embeddings into L_1, Robert Krauthgamer and Yuval Rabani, SODA 2006.

• Other interesting papers (deliberately excludes talks we will see at Princeton)

• Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method, Roman Vershynin, 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.

• 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.

• Low distortion embeddings for edit distance, Rafail Ostrovsky, Yuval Rabani, STOC 2005.

• Nonembeddability theorems via Fourier analysis, Subhash Khot and Assaf Naor, FOCS 2005.

• 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

• 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.

• , Rafail Ostrovsky, Yuval Rabani, STOC 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.

• The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into L1, Subhash Khot and Nisheeth Vishnoi, FOCS 2005.

• The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into L1, Subhash Khot and Nisheeth Vishnoi, FOCS 2005.

This is a weekly algorithms reading group

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

Mailing list for announcements:

• coming soon.

Suggestions for presentations

• Lower-Stretch Spanning Trees, M. Elkin, Y. Emek, D. Spielman, and S. Teng, STOC 2005.

• 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

• 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.

• Rafail Ostrovsky, Yuval Rabani: Low distortion embeddings for edit distance. STOC 2005.

• Nonembeddability theorems via Fourier analysis, Subhash Khot and Assaf Naor, FOCS 2005

by Venkatesan Guruswami and Prasad Raghavendra, FOCS 2006

• Compressed Sensing
  • "Error Correction via Linear Programming. Emmanuel J. Candes and Mark Rudelson and Terence Tao and Roman Vershynin.", FOCS 2005

Algorithms Reading Group

Moses Charikar

• 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

by Xi Chen and Xiaotie Deng, FOCS 2006

• Computing Nash Equilibria: Approximation and Smoothed Complexity

by Xi Chen, Xiaotie Deng and Shang-Hua Teng, FOCS 2006

• Metric embeddings
  • Lower-Stretch Spanning Trees,
    M. Elkin, Y. Emek, D. Spielman, and S. Teng, STOC 2005.
• Hardness of learning problems
  • New Results for Learning Noisy Parities and Halfspaces

by Vitaly Feldman and Parikshit Gopalan and Subhash Khot and Ashok Kumar Ponnuswami, FOCS 2006

• Hardness of Learning Halfspaces with Noise

by Venkatesan Guruswami and Prasad Raghavendra

• Integrality gaps for SDP relaxations
  • 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, to appear in STOC 2006.
• Orienteering and TSP with deadlines
  • Approximation Algorithms for Orienteering and Discounted-Reward TSP,
    Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, and Maria Minkoff, FOCS 2003.
  • Approximation Algorithms for Deadline-TSP,
    Nikhil Bansal, Avrim Blum, Shuchi Chawla, and Adam Meyerson, STOC 2004.
  • A Recursive Greedy Algorithm for Walks in Directed Graphs,
    Chandra Chekuri and Martin Pal, FOCS 2005.