Program

The conference will start at 8:50am on Monday, June 6, and the last talks will finish around 5:30pm on Wednesday, June 8.

A provisional program is available as a pdf file.

The following speakers will give invited presentations:

Survey presentations:

      • Costis Daskalakis (MIT)
        • Reduction from mechanism design to optimization
      • Aleksander Madry (MIT)
        • Fast graph algorithms and continuous optimization
      • Daniel Marx (Hungarian Academy of Sciences)
        • The optimality program for parameterized algorithms
      • Aaron Sidford (MIT)
        • Recent results on more efficient algorithms for graph problems and convex optimization
      • Virginia Vassilevska Williams (Stanford)
        • On complexity/hardness in P
      • Ryan Williams (Stanford)
        • New applications of the polynomial method to algorithm design

Invited presentations:

      • Stephen Alstrup (University of Copenhagen)
        • Recent results in labeling schemes (based on papers from STOC’15, FOCS’15, SODA’16)
      • Alexandr Andoni (Columbia University)
        • Optimal data-dependent hashing for approximate near neighbors (joint work with Ilya Razenshteyn), STOC’15
      • Yossi Azar (Tel Aviv University)
        • Speed scaling in the non-clairvoyant model (joint work with Nikhil Devanur, Zhiyi Huang, and Debmalya Panigrah), SPAA’15 best paper
      • Arturs Backurs (MIT)
        • Edit distance cannot be computed in strongly subquadratic time (unless SETH is false) (joint work with Piotr Indyk), STOC’15
      • Nikhil Bansal (Eindhoven University of Technology)
        • Minimizing flow-time on unrelated machines (joint work with Janardhan Kulkarni), STOC’15
      • Greg Bodwin (Stanford)
        • The 4/3 additive spanner exponent is tight (joint work with Amir Abboud), STOC’16; manuscript available at arXiv:1511.00700
      • Shiri Chechik (Tel Aviv University)
        • Approximate distance oracles with improved bounds, STOC’15
      • Ilias Diakonikolas (University of Southern California)
        • Hypothesis testing for structured probability distributions (joint work with Daniel M. Kane and Vladimir Nikishkin), based on SODA’15 and FOCS’15 papers
      • Mohsen Ghaffari (MIT)
        • An improved distributed algorithm for maximal independent set, SODA’16, best paper
      • Anupam Gupta (CMU)
        • Greedy algorithms for Steiner forest (joint work with Amit Kumar), STOC’15
      • Monika Henzinger (Universität Wien)
        • Using the primal-dual method to design dynamic graph algorithms (joint work with Sayan Bhattacharya and Giuseppe F. Italiano), based on SODA’15 and ICALP’15 papers
      • Ken-ichi Kawarabayashi (National Institute of Informatics)
        • Deterministic global minimum cut of a simple graph in near-linear time (joint work with Mikkel Thorup), STOC’15
      • Stephan Kreutzer (TU Berlin)
        • The directed grid theorem (joint work with Ken-ichi Kawarabayashi), STOC’15
      • Robert Krauthgamer (Weizmann Institute)
        • Sketching and embedding are equivalent for norms (joint work with Alexandr Andoni and Ilya P. Razenshteyn), STOC’15
      • Moshe Lewenstein (Bar Ilan University)
        • Clustered integer 3SUM via additive combinatorics (joint work with Timothy M. Chan), STOC’15
      • David Mount (University of Maryland)
        • A fast and simple algorithm for computing approximate Euclidean minimum spanning trees (joint work with Sunil Arya), SODA’16
      • Shayan Oveis Gharan (University of Washington)
        • Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP (joint work with Nima Anari), FOCS’15
      • Christian Sohler (TU Dortmund)
        • Testing cluster structure of graphs (joint work with Artur Czumaj and Pan Peng), STOC’2015
      • Clifford Stein (Columbia University)
        • Faster fully dynamic matchings with small approximation ratios (joint work with Aaron Bernstein), ICALP’2015 best paper and SODA’2016
      • Ola Svensson (EPFL)
        • Approximating ATSP by relaxing connectivity, FOCS’15
      • Huacheng Yu (Stanford)
        • An improved combinatorial algorithm for Boolean matrix multiplication, ICALP’15, best student paper