New Directions in Approximations Algorithms

February 22-28, 2015

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

Tim Roughgarden
Approximation and Algorithmic Game Theory
Constantinos 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)
Prasad Raghavendra
Lower Bounds on the Size of Semidefinite Programs (PDF)
David Steurer
Lower Bounds on Semidefinite Programming Relaxations
Raghu 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)
Avrim Blum
Connections Between Learning and Approximation
Sanjeev Arora
Linear Algebra ++ and Unsupervised Machine Learning
Satish Rao
Sherman’s Algorithm for Approximate Maximum Flow: Cut Approximation, Preconditioning and Multiplicative Weights
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)
Kunal Talwar
Approximation Algorithms and Differential Privacy
Shuchi Chawla
Approximate Optimality via Simple Tuthful Mechanisms
Roy Schwartz
Fast and Simple Algorithms for Submodular Maximization (PDF)
Nikhil Bansal
Independent Sets in Sparse Graphs (PDF)

→ View/download full agenda PDF


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

(Download Participants PDF)


Registration and Travel Assistance

Susan Gatewood
susan.gatewood(replace this with the @ sign)
(646) 747-9317

Meeting Questions and Assistance

Meghan Fazzi
Executive Assistant to Yuri Tschinkel, Simons Foundation
mfazzi(replace this with the @ sign)
(212) 524-6080

Reimbursement and Travel Policy


• Download Expense Policy
• Download Reimbursement Form

Any expenses not directly paid for by the Simons Foundation are subject to reimbursement based on the travel policy. Please review the policy and complete the provided reimbursement form when submitting your expenses. All expenses with original receipts and completed expense reimbursement form are due within SIXTY DAYS (60) after the conclusion of the symposium. Should you have any questions, please contact Meghan Fazzi.

Guest Policy

It is the foundation’s policy to discourage spouses, families or others from joining participants during the meeting. Participants who choose to invite guests to come before or stay on after the meeting do so at their own expense. The Simons Foundation will not cover expenses associated with such extensions.

Should you decide to extend your stay, the resort will honor the Simons Foundation group rate of $689/night for up to three additional nights. If you choose to bring a guest, your guest must depart by Sunday if coming before the symposium or arrive on Saturday if you are extending your stay at the end of the symposium.

« Back to Simons Symposia