New Directions in Approximations Algorithms (2015)
Organizers:
Sanjeev Arora, Princeton University
Uriel Feige, Weizmann Institute
Michel Goemans, Massachusetts Institute of Technology
David Shmoys, Cornell University
This is the second Simons Symposium on Approximation Algorithms for NP-hard problems. The first, in January 2013, focused on core techniques and problems of this field. The upcoming meeting is expected to also highlight how the notion of approximation has found uses in other areas, including mechanism design, combinatorial optimization, online algorithms, machine learning, big-data algorithms, differential privacy and discrepancy theory.
The schedule will be a mix of surveys and talks about new results. The structure will be informal and provide time for intense group discussions about open problems. Not all attendees will be expected to give long talks.
-
Agenda & Lecture Slides
Monday Tim Roughgarden
Approximation and Algorithmic Game TheoryConstantinos Daskalakis
Removing Mechanism to Algorithm Design (PDF)Bobby Kleinberg
Security Problems with Non-uniform Arrival Order (PDF)Mohit Singh
Linear Programs & Algorithms for Capacitated Facility Location (PDF)Tuesday Prasad Raghavendra
Lower Bounds on the Size of Semidefinite Programs (PDF)David Steurer
Lower Bounds on Semidefinite Programming RelaxationsRaghu Meka
Sum-of-Squares and Planted Clique (PDF)Moses Charikar
Spectral Embedding of k-cliques, Graph Partitioning and k-Means (PDF)Uriel Fiege
A Prediction Game (PDF)Wednesday Avrim Blum
Connections Between Learning and ApproximationSanjeev Arora
Linear Algebra ++ and Unsupervised Machine LearningSatish Rao
Sherman’s Algorithm for Approximate Maximum Flow: Cut Approximation, Preconditioning and Multiplicative WeightsThursday Nikhil Bansal & Thomas Rothvoss
Discrepency and Approximation (PDFs: Part I, Part II)Konstantin Makarychev
Solving Optimization Problems with Diseconomies of Scale via Decoupling (PDF)Ola Svensson
Approximating ATSP by Relaxing Connectivity (PDF)Julia Chuzoy
Excluded Grid Theorem: Improved and Simplified (PDF)Friday Kunal Talwar
Approximation Algorithms and Differential PrivacyShuchi Chawla
Approximate Optimality via Simple Tuthful MechanismsRoy Schwartz
Fast and Simple Algorithms for Submodular Maximization (PDF)Nikhil Bansal
Independent Sets in Sparse Graphs (PDF) -
Participants
Sanjeev Arora Princeton University Nikhil Bansal Eindhoven University of Technology Avrim Blum Carnegie Mellon University Moses Charikar Princeton University Shuchi Chawla University of Wisconsin Julia Chuzhoy Toyota Technological Institute at Chicago Costis Daskalakis MIT Irit Dinur Weizmann Institute of Science Uriel Feige Weizmann Institute of Science Michel Goemans MIT Bobby Kleinberg Cornell University Konstantin Makarychev Microsoft Research Raghu Meka Institute for Advanced Study Prasad Raghavendra UC Berkeley Satish Rao UC Berkeley Thomas Rothvoss University of Washington Tim Roughgarden Stanford University Roy Schwartz Princeton University David Shmoys Cornell University Mohit Singh Microsoft Research David Steurer Cornell University Ola Svensson École Polytechnique Fédérale de Lausanne Kunal Talwar Microsoft Research