Fall 2017

Bridging Continuous and Discrete Optimization

Aug. 16Dec. 15, 2017

Continuous and discrete optimization, historically, have followed two largely distinct trajectories. The study of discrete optimization has been intertwined with that of theoretical computer science: the foundations of computational complexity and algorithm design, including NP-completeness, approximation algorithms and inapproximability, all blossomed around the study of discrete optimization problems. In contrast, continuous optimization has been grounded in the well-developed mathematical theory of convex analysis and geometry. It has been inspired by numerous applications in operations research, statistics, control theory and, most recently, machine learning. The substantial overlap with scientific computing has led continuous optimization to become a basic tool in many areas of science that adopt continuous models to describe and understand natural phenomena.

While there have always been connections between the foundations of continuous and discrete optimization, the active areas of research in these two fields have significantly differed until recently. In the last decade, partly stimulated by the growth of machine learning and by the proliferation of massive datasets, a number of new research areas have emerged at the intersection of the two fields. The expanded interface between continuous and discrete optimization has already led to a number of breakthroughs in both areas, including, among many others, faster algorithms for maximum flow problems in graphs, improved interior-point method solvers, novel approaches for fundamental discrete problems such as the asymmetric traveling salesman problems, and stronger impossibility results on the capability of extended formulations to approximate NP-hard problems.

In this program, we aim to bring together these two communities and stimulate further interaction in areas of shared interest, examples of which can be found among the themes of the program workshops. We welcome participants from all areas of discrete and continuous optimization, as well as their applications.

Note: This is a "jumbo" program, and will run alone in its semester.  It will be roughly twice the size of a standard program.

This program is supported in part by the National Science Foundation, as part of the DIMACS/Simons Institute Collaboration on Bridging Continuous and Discrete Optimization.

sympa [at] lists [dot] simons [dot] berkeley [dot] edu (body: (Click here to subscribe to our announcements email list for this program.)


Aleksander Mądry (Massachusetts Institute of Technology; co-chair), Jan Vondrák (Stanford University; co-chair), Nikhil Bansal (Technische Universiteit Eindhoven), Nick Harvey (University of British Columbia), Dorit Hochbaum (UC Berkeley), Seffi Naor (Technion Israel Institute of Technology), Lorenzo Orecchia (Boston University), Pablo Parrilo (Massachusetts Institute of Technology), Benjamin Recht (UC Berkeley), Thomas Rothvoß (University of Washington)

Long-Term Participants (including Organizers):

Farid Alizadeh (Rutgers University), Zeyuan Allen-Zhu (Microsoft Research), Afonso Bandeira (Courant Institute, NYU), Nikhil Bansal (Technische Universiteit Eindhoven), Lenore Blum (Carenegie Mellon University), Manuel Blum (Carenegie Mellon University), Sébastien Bubeck (Microsoft Research Redmond), Deeparnab Chakrabarty (Dartmouth College), Moses Charikar (Stanford University), Ken Clarkson (IBM Almaden), Daniel Dadush (CWI), Damek Davis (Cornell University), Friedrich Eisenbrand (EPFL Switzerland), Alina Ene (Boston University), Maryam Fazel (University of Washington), Samuel Fiorini (Université Libre de Bruxelles), Anupam Gupta (Carnegie Mellon University), Leonid Gurvits (City University of New York), Moritz Hardt (UC Berkeley), Nick Harvey (University of British Columbia), Dorit Hochbaum (UC Berkeley), Stefanie Jegelka (Massachusetts Institute of Technology), Ravi Kannan (Microsoft Research India), Samir Khuller (University of Maryland), Fatma Kılınç-Karzan (Carnegie Mellon University), Alexandra Kolla (University of Illinois at Urbana-Champaign), Matthias Köppe (University of California, Davis), Robert Krauthgamer (Weizmann Institute), Jean-Bernard Lasserre (LAAS-CNRS, Toulouse), Monique Laurent (CWI Amsterdam), James R. Lee (University of Washington), Jon Lee (University of Michigan), Yin Tat Lee (University of Washington), Mike Luby (Qualcomm Inc), Shiqian Ma (The Chinese University of Hong Kong), Aleksander Mądry (Massachusetts Institute of Technology; co-chair), Monaldo Mastrolilli (IDSIA), Raghu Meka (UCLA), Seffi Naor (Technion Israel Institute of Technology), Huy Nguyen (Northeastern University), Rad Niazadeh (Stanford University), Sasho Nikolov (University of Toronto), Neil Olver (Vrije Universiteit Amsterdam), Lorenzo Orecchia (Boston University), Shayan Oveis Gharan (University of Washington), Pablo Parrilo (Massachusetts Institute of Technology), Sebastian Pokutta (Georgia Institute of Technology), Prasad Raghavendra (UC Berkeley), Benjamin Recht (UC Berkeley), Jim Renegar (Cornell University), Thomas Rothvoß (University of Washington), Amin Saberi (Stanford University), Laura Sanità (University of Waterloo), Piotr Sankowski (University of Warsaw), Roy Schwartz (Technion Israel Institute of Technology), Aaron Sidford (Stanford University), Nikhil Srivastava (UC Berkeley), Ola Svensson (EPFL Switzerland), Chaitanya Swamy (University of Waterloo), Prasad Tetali (Georgia Institute of Technology), Kim-Chuan Toh (National University of Singapore), Levent Tunçel (University of Waterloo), Lieven Vandenberghe (UCLA), László Végh (London School of Economics), Cynthia Vinzant (North Carolina State University), Nisheeth Vishnoi (Ecole Polytechnique Fédérale de Lausanne), Jan Vondrák (Stanford University; co-chair), Mengdi Wang (Princeton University), David Williamson (Cornell University), Stephen Wright (University of Wisconsin-Madison), Yinyu Ye (Stanford University), Rico Zenklusen (ETH Zürich)

Research Fellows:

Nima Anari (Stanford University), Parinya Chalermsook (Aalto University), Michael Cohen (Massachusetts Institute of Technology), Reza Eghbali (University of Washington), Swati Gupta (Massachusetts Institute of Technology), Robert Hildebrand (IBM Research), Rebecca Hoberg (University of Washington), Rasmus Kyng (Yale University), Bundit Laekhanukit (Weizmann Institute), Euiwoong Lee (Carnegie Mellon University), Cong Han Lim (University of Wisconsin-Madison), Aryan Mokhtari (University of Pennsylvania), Walaa Moursi (University of British Columbia), Kanstantsin Pashkovich (University of Waterloo), Ludwig Schmidt (Massachusetts Institute of Technology; Microsoft Research Fellow), Tselil Schramm (UC Berkeley; Google Research Fellow), Soledad Villar (University of Texas, Austin), Di Wang (UC Berkeley)

Visiting Graduate Students and Postdocs:

Jason Altschuler (Massachusetts Institute of Technology), Kyriakos Axiotis (Massachusetts Institute of Technology), Charles Carlson (University of Illinois, Urbana-Champaign), Niladri Chatterji (UC Berkeley), Jelena Diakonikolas (Boston University), Grace Dinh (UC Berkeley), Shashwat Garg (Eindhoven University of Technology), Benjamin Grimmer (Cornell University), Krystal Guo (Université Libre de Bruxelles), Fotis Iliopoulos (UC Berkeley), Tarun Kathuria (UC Berkeley), Koulik Khamaru (UC Berkeley), Christopher Liaw (University of British Columbia), Andre Linhares (University of Waterloo), Marco Macchia (Université Libre de Bruxelles), Aleksandar Makelov (Massachusetts Institute of Technology), Theo McKenzie (UC Berkeley), Sarah Morell (EPFL Switzerland), Alireza Rezaei (University of Washington), Andreas Schmid (Max Planck Institute, Saarbrücken), Jonah Sherman (UC Berkeley), Sahil Singla (Carnegie Mellon University), Yue Sun (University of Washington), Jakub Tarnawski (EPFL Switzerland), Matteo Tonelli (Gran Sasso Science Institute), Dimitris Tsipras (Massachusetts Institute of Technology), Daniel Vaz (Max Planck Institute, Saarbrücken), Adrian Vladu (Boston University), David Wajc (Carnegie Mellon University), Karol Węgrzycki (University of Warsaw), Lin Yang (Johns Hopkins University), Sheng Yang (University of Maryland), Chenyang Yuan (Massachusetts Institute of Technology)


Aug. 21Aug. 25, 2017


Nikhil Bansal (Technische Universiteit Eindhoven), Pablo Parrilo (Massachusetts Institute of Technology), Benjamin Recht (UC Berkeley)
Sep. 11Sep. 15, 2017


Chandra Chekuri (University of Illinois, Urbana-Champaign; chair), Nikhil Bansal (Technische Universiteit Eindhoven), Seffi Naor (Technion Israel Institute of Technology), Mohit Singh (Georgia Institute of Technology)
Oct. 2Oct. 6, 2017


Alexandr Andoni (Columbia University; chair), Maryam Fazel (University of Washington), Aleksander Mądry (Massachusetts Institute of Technology), Lorenzo Orecchia (Boston University), Benjamin Recht (UC Berkeley), Yinyu Ye (Stanford University)
Nov. 3, 2017


Benjamin Recht (UC Berkeley)
Nov. 6Nov. 9, 2017


Prasad Raghavendra (UC Berkeley; chair), Nick Harvey (University of British Columbia), Pablo Parrilo (Massachusetts Institute of Technology), Sebastian Pokutta (Georgia Institute of Technology), Cynthia Vinzant (North Carolina State University)
Nov. 17, 2017


Swati Gupta (Massachusetts Institute of Technology), David Williamson (Cornell University)
Nov. 27, 2017


Sébastien Bubeck (Microsoft Research Redmond), Aleksander Mądry (Massachusetts Institute of Technology)
Nov. 28Dec. 1, 2017


Sébastien Bubeck (Microsoft Research Redmond; chair), Moritz Hardt (UC Berkeley), Aleksander Mądry (Massachusetts Institute of Technology), Seffi Naor (Technion Israel Institute of Technology), Philippe Rigollet (Massachusetts Institute of Technology)
Dec. 8, 2017


Jelena Diakonikolas (Boston University), Rasmus Kyng (Yale University)

Program image: "Bridging Continuous and Discrete Optimization" by Thomas Rothvoß