HIGHLIGHTS OF ALGORITHMS

University of Copenhagen, June 14-16, 2019

Programme

Friday, June 14


9:00 - 10:00 Laszlo Vegh — Survey on approximation algorithms for the asymmetric traveling salesman problem.
10:00 - 10:30
Martin Grohe — A Faster Isomorphism Test for Graphs of Small Degree

Appeared in FOCS 2018; coauthored with Daniel Neuen and Pascal Schweitzer. Search for paper

10:30 - 11:00 Coffee Break
11:00 - 11:30
Shuichi Hirahara — Non-black-box Worst-case to Average-case Reductions within NP

Appeared in FOCS 2018. Search for paper

11:30 - 12:00
Josh Alman — Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Appeared in FOCS 2018; coauthored with Virginia Vassilevska Williams. Search for paper

12:00 - 12:30
Vera Traub — Beating the integrality ratio for s-t-tours in graphs

Appeared in FOCS 2018; coauthored with Jens Vygen. Search for paper

12:30 - 14:00 Lunch
14:00 - 15:30 Contributed talks 1
15:30 - 16:00 Coffee Break
16:00 - 17:00 James Lee — Survey on k-server.
17:00 - 17:30
Moses Charikar — Efficient Density Evaluation for Smooth Kernels

Appeared in FOCS 2018; coauthored with Arturs Backurs, Piotr Indyk and Paris Siminelakis. Search for paper

17:30 - 18:00
Sushant Sachdeva — Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions

Appeared in FOCS 2018; coauthored with Timothy Chu, Yu Gao, Richard Peng, Saurabh Sawlani and Junxing Wang. Search for paper

18:00 - 18:30
Michal Koucký — Approximating edit distance in sub quadratic time

Appeared in FOCS 2018; coauthored with Diptarka Chakraborty, Debarati Das, Elazar Goldenberg and Michael Saks. Search for paper

18:30 - 19:30 Poster session 1

Saturday, June 15


9:00 - 10:00 Thomas Vidick — Survey on recent advances in quantum computing.
10:00 - 10:30
Cliff Stein — A fast algorithm for knapsack via convolution and prediction

Appeared in STOC 2018; coauthored with Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi and Saeed Seddighin. Search for paper

10:30 - 11:00 Coffee Break
11:00 - 11:30
Sebastien Bubeck — k-server via multiscale entropic regularization

Appeared in STOC 2018; coauthored with Michael B. Cohen, James R. Lee, Yin Tat Lee and Aleksander Madry. Search for paper

11:30 - 12:00
Nima Anari — Planar Graph Perfect Matching is in NC

Appeared in FOCS 2018; coauthored with Vijay Vazirani. Search for paper

12:00 - 12:30
Greg Bodwin — On the Structure of Unique Shortest Paths in Graphs

Appeared in SODA 19. Search for paper

12:30 - 14:00 Lunch
14:00 - 15:30 Contributed talks 2
15:30 - 16:00 Coffee Break
16:00 - 17:00 Monika Henzinger — Survey on dynamic graph algorithm.
17:00 - 17:30
C. Seshadhriy — Finding forbidden minors in sublinear time: an $n^{1/2 + o(1)}$-query one-sided tester for minor closed properties

Appeared in FOCS 2018; coauthored with Akash Kumar and Andrew Stolmanz. Search for paper

17:30 - 18:00
Naveen Garg — Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time

Appeared in ; coauthored with Amit Kumar. Search for paper

18:00 - 19:00 Poster session 2
19:00 - 20:00 Business meeting

Sunday, June 16


9:00 - 10:00 Sergei Vassilvitskii — Survey on incorporating machine learning into traditional algorithm design and analysis.
10:00 - 10:30
Rico Zenklusen — Improved Approximation for Tree Augmentation: Saving by Rewiring

Appeared in STOC 2018; coauthored with Fabrizio Grandoni and Christos Kalaitzis. Search for paper

10:30 - 11:00 Coffee Break
11:00 - 11:30
Shayan Oveis Gharan — A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings

Appeared in STOC 2018; coauthored with Anna Karlin and Robbie Weber. Search for paper

11:30 - 12:00
Bundit Laekhanukit — On the parameterized complexity of approximating dominating set

Appeared in STOC 2018; coauthored with Karthik C. S. and Pasin Manurangsi. Search for paper

12:00 - 12:30
Kunal Talwar — Privacy Amplification by Iteration

Appeared in FOCS 2018; coauthored with Vitaly Feldman, Ilya Mironov and Abhradeep Thakurta. Search for paper

12:30 - 14:00 Lunch
14:00 - 15:30 Contributed talks 3
15:30 - 16:00 Coffee Break
16:00 - 17:00 Timothy Chan — Survey on 3SUM/kSUM algorithms/decision trees and 3SUM/kSUM hardness.
17:00 - 17:30
Sungjin Im — Online load balancing on related machines

Appeared in STOC 2018; coauthored with Nathaniel Kell, Debmalya Panigrahi and Maryam Shadloo. Search for paper

17:30 - 18:00
Shay Moran — Near-optimal linear decision trees for k-SUM and related problems

Appeared in STOC 2018; coauthored with Daniel M. Kane and Shachar Lovett. Search for paper