HIGHLIGHTS OF ALGORITHMS

TU Berlin, June 9-11, 2017

Survey Speakers


László Babai

University of Chicago

Tim Roughgarden

Stanford University

Nikhil Bansal

TU Eindhoven

Sanjeev Arora

Princeton University

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 (MIT) - 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 - 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 (ETH) - 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


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


Aviad Rubenstein (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