HIGHLIGHTS OF ALGORITHMS

TU Berlin, June 9-11, 2017

Survey Speakers



Sanjeev Arora (Princeton University)

Unsupervised learning to uncover semantics of data and language


Claire Mathieu (CNRS, École normale supérieure)

Local search for clustering problems



László Babai (University of Chicago)

Group theory and combinatorics: The Graph Isomorphism problem


Tim Roughgarden (Stanford University)

Beyond Worst-Case Analysis


Nikhil Bansal (TU Eindhoven)

Algorithmic Discrepancy beyond Partial Coloring

Invited Speakers


Karl Bringmann (MPI for Informatics) - Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product (FOCS 2016)
Co-Authors: Fabrizio Grandoni, Barna Saha and Virginia Vassilevska Williams


Constantinos Daskalakis (MIT) - Learning in Auctions: Regret is Hard, Envy is Easy (FOCS 2016)
Co-Author: Vasilis Syrgkanis


Ilias Diakonikolas (USC) - Robust Estimators in High Dimensions without the Computational Intractability (FOCS 2016)
Co-Authors: Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra and Alistair Stewart


Zachary Friggstad (U. Alberta) - Local Search Yields a PTAS for k-Means in Doubling Metrics (FOCS 2016)
Co-Authors: Mohsen Rezapour and Mohammad Salavatipour


Mohsen Ghaffari (ETH) - An Improved Distributed Algorithm for Maximal Independent Set (SODA 2016)


Bart M. P. Jansen (TU Eindhoven) - Fine-grained complexity analysis of two classic TSP variants (ICALP 2016)
Co-Authors: Mark de Berg, Kevin Buchin and Gerhard J. Woeginger


David Karger (MIT) - Faster and Simpler Network (Un)reliability Estimation (FOCS 2016)


Sanjeev Khanna (UPenn) - On Estimating Maximum Matching Size in Graph Streams (SODA 2017)
Co-Authors: Sepehr Assadi and Yang Li


Mathias Bæk T. Knudsen (U. Copenhagen) - Linear Hashing is Awesome (FOCS 2016)


Simon MacKenzie (Carnegie Mellon University) - A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents (FOCS 2016)
Co-Author: Haris Aziz


Aleksander Madry (MIT) - Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in O(m10/7 log W) Time (SODA 2017)
Co-Authors: Michael B. Cohen, Piotr Sankowski and Adrian Vladu


Marco Mondelli (Stanford) - Reed-Muller Codes Achieve Capacity on Erasure Channels (STOC 2016)
Co-Authors: Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Şaşoğlu, and Rüdiger Urbanke


Renato Paes-Leme (Google) - Computing Walrasian Equilibria: Fast Algorithms and Structural Properties (SODA 2017)
Co-Author: Sam Chiu-Wai Wong


Merav Parter (MIT) - MST in Log-Star Rounds of Congested Clique (PODC 2016)
Co-Author: Mohsen Ghaffari


Ilya P. Razenshteyn (MIT) - Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing (SoCG 2016)
Co-Author: Alexandr Andoni


Aviad Rubinstein (Berkeley) - Settling the Complexity of Computing Approximate Two-player Nash Equilibria (STOC 2016)


Ami Paz (The Technion) - A (2 + ε )-Approximation for Maximum Weight Matching in the Semi-Streaming Model (SODA 2017)
Co-Author: Gregory Schwartzman


Sushant Sachdeva (Google) - Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple (FOCS 2016)
Co-Author: Rasmus Kyng


Aravind Srinivasan (U. Maryland) - Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines (STOC 2016)
Co-Authors: Nikhil Bansal and Ola Svensson


Gregory Valiant (Stanford) - Instance Optimal Learning of Discrete Distributions (STOC 2016)
Co-Author: Paul Valiant


S. Matthew Weinberg (Princeton) - A Duality Based Unified Approach to Bayesian Mechanism Design (STOC 2016)
Co-Authors: Yang Cai and Nikhil Devanur