HIGHLIGHTS OF ALGORITHMS

Vrije Universiteit Amsterdam, June 4-6, 2018

Survey speakers

Invited speakers

    Amir Abboud (Stanford University) — Distributed PCP Theorems for Hardness of Approximation in P (FOCS 2017)
    Co-authors: Aviad Rubinstein and Ryan Williams

    Nikhil Bansal (CWI & TU Eindhoven) — Faster Space-Efficient Algorithms for Subset Sum and k-Sum (STOC 2017)
    Co-authors: Shashwat Garg, Jesper Nederlof and Nikhil Vyas

    Aaron Bernstein (TU Berlin) — Online Bipartite Matching with Amortized O(log2 n) Replacements (SODA 2018)
    Co-authors: Jacob Holm and Eva Rotenberg

    Sergio Cabello (University of Ljubljana) — Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs (SODA 2017)

    Parinya Chalermsook (Aalto University) — From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More (FOCS 2017)
    Co-authors: Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai and Luca Trevisan

    Moses Charikar (Stanford University) — A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics (COLT 2017)
    Co-authors: Yuchen Zhang and Percy Liang

    Chandra Chekuri (University of Illinois, Urbana Champagne) — Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time (FOCS 2017)
    Co-author: Kent Quanrud

    Anindya De (Northwestern University) — Trace Reconstruction with exp(O(n1/3)) Samples + Optimal Mean-based Algorithms for Trace Reconstruction (STOC 2017)
    Co-authors: (Independent works) Fedor Nazarov and Yuval Peres + Anindya De, Ryan O'Donnell and Rocco A. Servedio

    Yuval Filmus (Technion) — Twenty (Simple) Questions (STOC 2017)
    Co-authors: Yuval Dagan, Ariel Gabon and Shay Moran

    Magnús Halldorsson (Reykjavik University) — Universal Framework for Wireless Scheduling Problems (ICALP 2017)
    Co-authors: Eyjólfur I. Ásgeirsson and Tigran Tonoyan

    Jonathan Kelner (MIT) — Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs (STOC 2017)
    Co-authors: Michael B. Cohen, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford and Adrian Vladu

    Sanjeev Khanna (University of Pennsylvania) — Randomized composable coresets for matching and vertex cover (SPAA 2017)
    Co-author: Sepehr Assadi

    Pasin Manurangsi (UC Berkeley) — Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph (STOC 2017)

    Krzysztof Nowicki (University of Wrocław) — MST in O(1) Round of Congested Clique (SODA 2018)
    Co-author: Tomasz Jurdzinski

    Rotem Oshman (Tel-Aviv University) — A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness (FOCS 2017)
    Co-author: Mark Braverman

    Seth Pettie (University of Michigan) — A Time Hierarchy Theorem for the LOCAL Model (FOCS 2017)
    Co-author: Yi-Jun Chang

    Tselil Schramm (Harvard & MIT) — The Power of Sum-of-Squares for Detecting Hidden Structures (FOCS 2017)
    Co-authors: Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra and David Steurer

    Uri Stemmer (Weizmann Institute) — Practical Locally Private Heavy Hitters (NIPS 2017)
    Co-authors: Raef Bassily, Kobbi Nissim and Abhradeep Thakurta

    Inbal Talgam-Cohen (Hebrew University of Jerusalem) — Approximate modularity revisited (STOC 2017)
    Co-authors: Uriel Feige and Michal Feldman

    Vera Traub (University of Bonn) — Approaching 3/2 for the s-t-path TSP (SODA 2018)
    Co-author: Jens Vygen