Fall 2016

Algorithms and Uncertainty

Aug. 17Dec. 16, 2016
Traditionally in theoretical computer science it is assumed that one has complete uncertainty about an instance before it is handed to an algorithm (i.e., worst-case analysis) and complete certainty afterwards (i.e., the instance is fully specified). In practice, however, often neither of these assumptions is quite correct. Instances of optimization problems arising from different application domains, such as SAT instances arising from verification or clustering instances arising from AI applications, often have significant structure. Furthermore, when the instance is first presented, often the objective or model or input isn't completely known; examples include jobs with unknown runtimes, stochasticity in robot motion planning, and unknown agent types in mechanism design.
As a consequence, results from theoretical computer science can be simultaneously too pessimistic (e.g., giving strong hardness of approximation for problems where heuristic methods have significant success) and too optimistic (e.g., producing algorithms that cannot be used due to their brittleness to the instance specification). Both of these issues are fundamentally related, with a strong and vital interplay that incorporates topics such as smoothed analysis, semi-random models, instance-stability notions, and stochastic and robust optimization.
The research programs in these directions have gained considerable momentum lately, making it an opportune time to map out and jointly investigate the future. This program will bring together researchers to develop meaningful alternatives to worst-case analysis of algorithms, using ideas from machine learning, stability analysis and stochastic optimization. The program will also explore new methods for addressing uncertainty in instance specifications, including ideas from control theory and convex optimization.


Anupam Gupta (Carnegie Mellon University; co-chair), Stefano Leonardi (Sapienza University of Rome; co-chair), Avrim Blum (Carnegie Mellon University), Robert Kleinberg (Cornell University), Eli Upfal (Brown University), Adam Wierman (California Institute of Technology)

Long-Term Participants (including Organizers):

Nir Ailon (Technion Israel Institute of Technology), Susanne Albers (Technische Universität München), Aris Anagnostopoulos (Sapienza University of Rome), Peter Auer (University of Leoben), Yossi Azar (Tel Aviv University), Nikhil Bansal (Technische Universiteit Eindhoven), Peter Bartlett (UC Berkeley), Eilyan Bitar (Cornell University), Avrim Blum (Carnegie Mellon University), Nicolò Cesa-Bianchi (University of Milan), Shiri Chechik (Tel Aviv University), Edith Cohen (Google Research), Artur Czumaj (University of Warwick), Amit Daniely (Google Research), Amos Fiat (Tel Aviv University), Fabrizio Grandoni (IDSIA), Anupam Gupta (Carnegie Mellon University; co-chair), Mohammad Hajiaghayi (University of Maryland), Longbo Huang (Tsinghua University), Sungjin Im (UC Merced), Ravi Kannan (Microsoft Research India), Anna Karlin (University of Washington), Robert Kleinberg (Cornell University), Elias Koutsoupias (University of Oxford), Ravi Kumar (Google), Stefano Leonardi (Sapienza University of Rome; co-chair), Kevin Leyton-Brown (University of British Columbia), Jian Li (Tsinghua University), Katrina Ligett (Hebrew University and Caltech), Aleksander Mądry (Massachusetts Institute of Technology), Yishay Mansour (Tel Aviv University), Ruta Mehta (University of Illinois, Urbana-Champaign), Jamie Morgenstern (University of Pennsylvania), Kamesh Munagala (Duke University), Viswanath Nagarajan (University of Michigan), Seffi Naor (Technion Israel Institute of Technology), Kameshwar Poolla (UC Berkeley), Kirk Pruhs (University of Pittsburgh), Ram Rajagopal (Stanford University), Satish Rao (UC Berkeley), Benjamin Recht (UC Berkeley), Rhonda Righter (UC Berkeley), Tim Roughgarden (Stanford University), Piotr Sankowski (University of Warsaw), C. Seshadhri (UC Santa Cruz), Jay Sethuraman (Columbia University), Cliff Stein (Columbia University), Chaitanya Swamy (University of Waterloo), Marc Uetz (University of Twente), Eli Upfal (Brown University), Marilena Vendittelli (Sapienza University of Rome), Maria Vlasiou (Eindhoven University of Technology), Jean Walrand (UC Berkeley), Gideon Weiss (University of Haifa), Adam Wierman (California Institute of Technology), Bert Zwart (CWI Amsterdam)

Research Fellows:

Ilan Cohen (Tel Aviv University), Varun Gupta (University of Chicago), Thomas Kesselheim (Max-Planck-Institute for Informatics and Saarland University), Marco Molinaro (PUC-Rio de Janeiro; Microsoft Research Fellow), Benjamin Moseley (Washington University in St. Louis), Debmalya Panigrahi (Duke University), Xiaorui Sun (Columbia University; Google Research Fellow), Matt Weinberg (Princeton University), Qiaomin Xie (University of Illinois at Urbana-Champaign)

Visiting Graduate Students and Postdocs:

Angelos Aveklouris (Eindhoven University of Technology), Frank Ban (UC Berkeley), Chris Cameron (University of British Columbia), Niangjun Chen (California Institute of Technology), Sina Dehghani (University of Maryland), Grace Dinh (UC Berkeley), Alon Eden (Tel Aviv University), Talya Eden (Tel Aviv University), Soheil Ehsani (University of Maryland), Marek Eliáš (Technische Universiteit Eindhoven), Patric Fulop (University of Edinburgh), Kira Goldner (University of Washington), Guru Guruganesh (Carnegie Mellon University), Bart Kamphorst (CWI Amsterdam), Xiang Li (UC Berkeley), Raphael Louca (Cornell University), Pasin Manurangsi (UC Berkeley), Tommaso Nesti (CWI Amsterdam), Aviad Rubinstein (UC Berkeley), Tselil Schramm (UC Berkeley), Saeed Seddighin (University of Maryland), Sahil Singla (Carnegie Mellon University), Fiona Sloothaak (Eindhoven University of Technology), Seeun William Umboh (Technische Universiteit Eindhoven), Shai Vardi (Caltech), David Wajc (Carnegie Mellon University), Jakub Łącki (Sapienza University of Rome)


Aug. 22Aug. 26, 2016


Avrim Blum (Carnegie Mellon University), Anupam Gupta (Carnegie Mellon University), Robert Kleinberg (Cornell University), Stefano Leonardi (Sapienza University of Rome), Eli Upfal (Brown University), Adam Wierman (California Institute of Technology)
Sep. 19Sep. 23, 2016


Nikhil Bansal (Technische Universiteit Eindhoven; chair), Shipra Agrawal (Columbia University), Robert Kleinberg (Cornell University), Kamesh Munagala (Duke University), Jay Sethuraman (Columbia University), Adam Wierman (California Institute of Technology)
Nov. 14Nov. 18, 2016


Avrim Blum (Carnegie Mellon University; chair), Nir Ailon (Technion Israel Institute of Technology), Nina Balcan (Carnegie Mellon University), Ravi Kumar (Google), Kevin Leyton-Brown (University of British Columbia), Tim Roughgarden (Stanford University)
Dec. 4Dec. 6, 2017


Anupam Gupta (Carnegie Mellon University; co-chair), Stefano Leonardi (Sapienza University of Rome; co-chair), Avrim Blum (Carnegie Mellon University), Robert Kleinberg (Cornell University), Eli Upfal (Brown University), Adam Wierman (California Institute of Technology)

Note: In addition to the above workshops, the workshop "Uncertainty in Computation" in the companion program on "Logical Structures in Computation" is organized jointly with this program.

Nikhil Bansal will be teaching a course at UC Berkeley this Fall 2016, CS 294-128: Algorithms and UncertaintyThis course will be self-contained, but run in parallel to the Simons Institute semester on Algorithms and Uncertainty. One goal of the class will be to provide graduate students with sufficient background to participate fully in the Simons Institute semester. There will be occasional guest speakers from the Simons Institute program, presenting recent research results related to course materials.

Program image: Avrim Blum and Anupam Gupta.