HIGHLIGHTS OF ALGORITHMS

University of Copenhagen, June 14-16, 2019

Survey speakers:

Monika Henzinger (University of Vienna) - Survey on dynamic graph algorithm

Thomas Vidick (California Institute of Technology) - Survey on recent advances in quantum computing.

Laszlo Vegh (London School of Economics) - Survey on approximation algorithms for the asymmetric traveling salesman problem.

James Lee (University of Washington) - Survey on k-server.

Timothy Chan (University of Illinois at Urbana-Champaign) - Survey on 3SUM/kSUM algorithms/decision trees and 3SUM/kSUM hardness.

Sergei Vassilvitskii (Google, New York) - Survey on incorporating machine learning into traditional algorithm design and analysis.

Invited talks:

Martin Grohe (RWTH Aachen University) - A Faster Isomorphism Test for Graphs of Small Degree (FOCS 2018) - Co-authors: Daniel Neuen and Pascal Schweitzer

Josh Alman (MIT) - Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication (FOCS 2018) - Co-authors: Virginia Vassilevska Williams

Nima Anari (Stanford University) - Planar Graph Perfect Matching is in NC (FOCS 2018) - Co-authors: Vijay Vazirani

Michal Kouck√Ĺ (Charles University) - Approximating edit distance in sub quadratic time (FOCS 2018) - Co-authors: Diptarka Chakraborty, Debarati Das, Elazar Goldenberg and Michael Saks

Naveen Garg (IIT Delhi) - Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time - Co-authors: Amit Kumar

Vera Traub (University of Bonn) - Beating the integrality ratio for s-t-tours in graphs (FOCS 2018) - Co-authors: Jens Vygen

Rico Zenklusen (ETH Zurich) - Improved Approximation for Tree Augmentation: Saving by Rewiring (STOC 2018) - Co-authors: Fabrizio Grandoni and Christos Kalaitzis

Shayan Oveis Gharan (University of Washington) - A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings (STOC 2018) - Co-authors: Anna Karlin and Robbie Weber

Greg Bodwin (MIT) - On the Structure of Unique Shortest Paths in Graphs (SODA 19) - Co-authors:

Cliff Stein (Columbia University) - A fast algorithm for knapsack via convolution and prediction (STOC 2018) - Co-authors: MohammadHossein Bateni, MohammadTaghi Hajiaghayi and Saeed Seddighin

Sungjin Im (University of California at Merced) - Online load balancing on related machines (STOC 2018) - Co-authors: Nathaniel Kell, Debmalya Panigrahi and Maryam Shadloo

C. Seshadhriy (University of California, Santa Cruz) - Finding forbidden minors in sublinear time: an $n^{1/2 + o(1)}$-query one-sided tester for minor closed properties (FOCS 2018) - Co-authors: Akash Kumar and Andrew Stolmanz

Shay Moran (Technion) - Near-optimal linear decision trees for k-SUM and related problems (STOC 2018) - Co-authors: Daniel M. Kane and Shachar Lovett

Bundit Laekhanukit (Shanghai University of Finance and Economics) - On the parameterized complexity of approximating dominating set (STOC 2018) - Co-authors: Karthik C. S. and Pasin Manurangsi

Sebastien Bubeck (Microsoft Research, Redmond) - k-server via multiscale entropic regularization (STOC 18) - Co-authors: Michael B. Cohen, James R. Lee, Yin Tat Lee and Aleksander Madry

Sushant Sachdeva (University of Toronto) - Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions (FOCS 2018) - Co-authors: Timothy Chu, Yu Gao, Richard Peng, Saurabh Sawlani and Junxing Wang

Kunal Talwar (Google Brain) - Privacy Amplification by Iteration (FOCS 2018) - Co-authors: Vitaly Feldman, Ilya Mironov and Abhradeep Thakurta

Moses Charikar (Stanford University) - Efficient Density Evaluation for Smooth Kernels (FOCS 2018) - Co-authors: Arturs Backurs, Piotr Indyk and Paris Siminelakis

Shuichi Hirahara (University of Tokyo) - Non-black-box Worst-case to Average-case Reductions within NP (FOCS 2018) - Co-authors: