About
Over the past decade there has been a revolution in the theoretical foundations for obtaining provably fast algorithms for foundational problems in theoretical computer science. For problems ranging from maximum flow, to global minimum cut, to linear system solving, and beyond there have been breakthrough after breakthrough in improving asymptotic running times. Though classic theory had well-established the polynomial time solvability of these problems, the optimal running time for solving them had remained open; excitingly, recent work has shown that some of these problems can be solved in nearly linear time in broad regimes.
Beyond the foundational nature of these results and the modern motivations for faster algorithms, this suite of algorithmic advances is particularly exciting due to the wide range of tools they employ and the non-trivial interplay between them. These fast algorithms apply continuous optimization methods to solve combinatorial problems, dynamic data structures to solve static problems, sketching techniques to solve problems without memory limitations, and more. In some cases these faster algorithms have then in turn led to improvements for these tools, e.g. optimization techniques have been used in sketching routines and to yield improved dynamic graph algorithms. There have even been recent instances where a large suite of continuous, combinatorial, dynamic data structures, and sketching techniques are all combined for a faster algorithm for a single problem.
The central goal of the proposed program is to add further fuel to this budding area of research. The program will bring together experts in dynamic graphs, sketching, and optimization towards the common goal of furthering this confluence of advanced algorithmic techniques for breakthrough results. The bootcamp, workshops, and broader program activities will all be designed with the goal of advancing the foundations of each area, developing new connections between the areas, and making new advances at their intersection.
Click here to subscribe to our news and events to learn more about this and other events.
Organizers:
Alina Ene (Boston University), Monika Henzinger (University of Vienna), Yin-Tat Lee (University of Washington), Jelani Nelson (UC Berkeley), Aaron Sidford (Stanford University)
Long-Term Participants (including Organizers):
Haim Kaplan (Tel-Aviv University), Deeksha Adil (ETH Zurich), Sayan Bhattacharya (University of Warwick), Chandra Chekuri (University of Illinois, Urbana-Champaign), Edith Cohen (Google Research, Tel Aviv University), Daniel Dadush (Carnegie Mellon University), Alina Ene (Boston University), Maryam Fazel (University of Washington), Gramoz Goranci (University of Vienna), Anupam Gupta (Carnegie Mellon University), Monika Henzinger (IST Austria), Michael Kapralov (EPFL), Valerie King (University of Victoria), Philip Klein (Brown University), Rasmus Kyng (ETH Zurich), Yin-Tat Lee (University of Washington), Jason Li (Simons Institute), Andrew McGregor (UMass Amherst), Bento Natura (Georgia Institute of Technology), Yasamin Nazari (VU Amsterdam), Jelani Nelson (UC Berkeley), James Orlin (Massachusetts Institute of Technology), Debmalya Panigrahi (Duke University), Kent Quanrud (Purdue University), Sushant Sachdeva (University of Toronto), Piotr Sankowski (IDEAS NCBR, University of Warsaw, MIM Solutions), Thatchaphol Saranurak (University of Michigan), Aaron Sidford (Stanford University), Zhao Song (Adobe Research), He Sun (University of Edinburgh), Mikkel Thorup (University of Copenhagen), Nisheeth Vishnoi (Yale University), Adrian Vladu (CNRS, IRIF, Université Paris Cité), Jan Vondrak (Stanford University), David Woodruff (Carnegie Mellon University), Yinyu Ye (Stanford University)
Research Fellows:
Arun Jambulapati (University of Washington), Shunhua Jiang (Columbia University), Quanquan Liu (Northwestern University), Bento Natura (Georgia Institute of Technology), Nicole Wein (Rutgers University), Sorrachai Yingchareonthawornchai (Aalto University)
Visiting Graduate Students:
Ruoxu Cen (Duke University), Ming Ding (ETH Zurich), Dan Dorfman (Tel-Aviv University), Ekaterina Kochetkova (EPFL), Er Lu Lawrence Li (University of Toronto), Yaowei Long (University of Michigan), Peter Macgregor (University of Edinburgh), Mikhail Makarov (EPFL), Simon Carlo Meierhans (ETH Zurich), Ta Duy Nguyen (Boston University), Akshay Ramachandran (CWI), Kshiteej Sheth (EPFL), Weronika Wrosz-Kaminska (EPFL), Lichen Zhang (Massachusetts Institute of Technology), Yibin Zhao (University of Toronto)