# HIGHLIGHTS OF ALGORITHMS

University of Copenhagen, June 14-16, 2019

# Programme

All talks take place in the Auditorium 01

### Friday, June 14

 8:15 - 8:45 Registration and Coffee 8:45 - 8:55 Welcome, Anti-Harassment Policy, and Practical Info 9:00 - 9:55 Laszlo Vegh — Survey on approximation algorithms for the asymmetric traveling salesman problem The talk will give an overview on recent developments on the asymmetric traveling salesman problem (ATSP). In contrast to the symmetric problem variant, where the Christofides-Serdyukov algorithm gives a simple 3/2-approximation, no constant-factor approximation algorithm has been known until recently. The talk will give an overview of the different approaches that have lead to improved approximation guarantees over the last decade. These broadly fall into two classes: approaches that maintain connectivity but relax the Eulerian degree constraints, and approaches that maintain Eulerian degree constraints but relax connectivity. I will give more detail of our recent result with Svensson and Tarnawski, that followed the second approach to obtain the first constant-factor approximation for ATSP. Our techniques build upon Svensson’s earlier constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem. 10:00 - 10:25 Martin Grohe — A Faster Isomorphism Test for Graphs of Small Degree In a recent breakthrough, Babai (STOC 2016) gave quasipolynomial graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our algorithms runs in time n^polylog(d), where n is the number of vertices of the input graph and d is the maximum degree. The best previous isomorphism test for graphs of maximum degree d due to Babai, Kantor and Luks (FOCS 1983) runs in time n^O(d/log d). (Joint work with Daniel Neuen and Pascal Schweitzer.) 10:30 - 11:00 Coffee Break 11:00 - 11:25 Shuichi Hirahara — Non-black-box Worst-case to Average-case Reductions within NP There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of NP: Several results suggest that black-box worst-case to average-case reductions are not likely to be used for reducing any worst-case problem outside coNP to a distributional NP problem. In this talk, we present the first non-black-box worst-case to average-case reduction from a problem conjectured to be outside coNP to a distributional NP problem. Specifically, we consider the minimum time-bounded Kolmogorov complexity problem (MINKT), and prove that there exists a zero-error randomized polynomial-time algorithm approximating the minimum time-bounded Kolmogorov complexity k within an additive error of roughly $\sqrt{k}$ if its average-case version admits an errorless heuristic polynomial-time algorithm. We observe that the approximation version of MINKT is Random 3SAT-hard, and more generally it is harder than avoiding any polynomial-time computable hitting set generator that extends its seed of length n by roughly $\sqrt{n}$, which provides strong evidence that the approximation problem is outside coNP and thus our reductions are non-black-box. Our reduction can be derandomized at the cost of the quality of the approximation. We also show that, given a truth table of size $2^n$, approximating the minimum circuit size within a factor of $2^{(1 - \epsilon) n}$ is in $\BPP$ for some constant $\epsilon > 0$ if and only if its average-case version is easy. Our results can be seen as a new approach for excluding Heuristica. In particular, proving NP-hardness of the approximation versions of MINKT or the Minimum Circuit Size Problem (MCSP) is sufficient for establishing an equivalence between the worst-case and average-case hardness of NP. 11:30 - 11:55 Josh Alman — Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication We study the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser method of Strassen, and the Group theoretic approach of Cohn and Umans. We define a vast generalization based on degenerations which subsumes these two approaches, which we call the Universal method. We then design a suite of techniques for proving lower bounds on the value of omega, the exponent of matrix multiplication, which can be achieved by algorithms using many tensors T and the Universal method. Our main result is that a large class of tensors generalizing the Coppersmith-Winograd tensor CW_q cannot be used within the Universal method to show a bound on omega better than 2.16805, for any q. In this talk, I will give an overview of the known approaches to designing matrix multiplication algorithms, the Universal method, and our lower bound. The content will be based on joint work with Virginia Vassilevska Williams in FOCS 2018, and follow-up work to appear in CCC 2019. 12:00 - 12:25 Vera Traub — Beating the integrality ratio for s-t-tours in graphs The s-t-path TSP is the variant of the traveling salesman problem in which the endpoints of the tour are given and distinct. In this talk we consider the important special case of the s-t-path TSP in unit weight graphs, the s-t-path graph TSP. Among various variants of the traveling salesman problem, the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this work, we go below this threshold: we devise a polynomial-time algorithm for the s-t-path graph TSP with approximation ratio 1.497. Our algorithm can be viewed as a refinement of the 3/2-approximation algorithm by Sebő and Vygen [2014], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics). This is joint work with Jens Vygen. 12:30 - 14:00 Lunch (provided) 14:00 - 15:30 Contributed talks 1 15:30 - 16:00 Coffee Break 16:00 - 16:55 James Lee — Recent progress on regularization in competitive analysis One of the beautiful and mysterious aspects of online optimization is the design of clever potential functions for analyzing the competitive ratio of a given algorithm. Recent progress on some of the oldest problems (k-server and MTS) suggests a theory in which the potential function itself is central and automatically gives rise to an algorithm: Gradient descent on the natural objective, regularized by the potential. There are strong connections to the field of online learning, and future directions even suggest a tantalizing connection to deep learning. 17:00 - 17:25 Moses Charikar — Efficient Density Evaluation for Smooth Kernels Given a kernel function k(.,.) and a dataset P ⊂ ℝd , the kernel density function of P at a point x ∈ ℝd is equal to KDFP(x):= 1⁄|P| ∑y ∈ P k(x,y) . Kernel density evaluation has numerous applications, in scientific computing, statistics, computer vision, machine learning and other fields. In all of them it is necessary to evaluate KDFP(x) quickly, often for many inputs x and large point-sets P . In this paper we present a collection of algorithms for efficient KDF evaluation under the assumptions that the kernel k is "smooth", i.e. the value changes at most polynomially with the distance. This assumption is satisfied by several well-studied kernels, including the (generalized) t-student kernel and rational quadratic kernel. For smooth kernels, we give a data structure that, after O(dn log (Φ n)∕ϵ2) preprocessing, estimates KDFP(x) up to a factor of 1 ± ϵ in O(d log(Φ n)∕ϵ2) time, where Φ is the aspect ratio. The log(Φn) term can be further replaced by log(n) under an additional decay condition on k, which is satisfied by the aforementioned examples. We further extend the results in two ways. First, we use low-distortion embeddings to extend the results to kernels defined for spaces other than ℓ2 . The key feature of this reduction is that the distortion of the embedding affects only the running time of the algorithm, not the accuracy of the estimation. As a result, we obtain (1 ± ϵ)-approximate estimation algorithms for kernels over other ℓp norms, Earth-Mover Distance, and other metric spaces. Second, for smooth kernels that are decreasing with distance, we present a general reduction from density estimation to approximate near neighbor in the underlying space. This allows us to construct algorithms for general doubling metrics, as well as alternative algorithms for ℓp norms and other spaces. (Joint work with Arturs Backurs, Piotr Indyk and Paris Siminelakis in FOCS 2018) 17:30 - 17:55 Sushant Sachdeva — Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions We introduce short cycle decompositions -- a decomposition of a graph into edge-disjoint cycles of nearly constant length, plus a small number of extra edges, and give fast algorithms for computing such a decomposition. We utilize these decompositions to prove several new results in graph sparsification, including: Finding sparse spectral sparsifiers of a graph, with the same degrees as the original graphs. Finding very sparse graphs whose effective resistances are similar to the effective resistance of the original graph. Computing effective resistances of all edges in a graph, in the fastest known time. And more. This is joint work with Timothy Chu, Yu Gao, Richard Peng, Saurabh Sawlani, and Junxing Wang, and appeared at FOCS 2018. 18:00 - 18:25 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 - 9:55 Thomas Vidick — Survey on quantum program checking and quantum multiprover interactive proof systems The invention of interactive proof systems by Babai and Goldwasser et al. combined with the idea of program checking by Blum and Kannan to spawn an immensely productive line of work at the intersection of complexity theory, cryptography and algorithms, leading in particular to the PCP theorem and subsequent results on hardness of approximation. In the talk I will survey the status of a similar line of work relating quantum program checking, quantum interactive proofs and hardness of approximation for quantum problems. I will discuss recent exciting progress on the complexity of entangled-prover interactive proof systems and its relevance for questions from the foundations of quantum mechanics to the quantum PCP conjecture. 10:00 - 10:25 Cliff Stein — A fast algorithm for knapsack via convolution and prediction It has been studied extensively from theoretical as well as practical perspectives as it is one of the most well-known NP-hard problems. The goal is to pack a knapsack of size t with the maximum value from a collection of n items with given sizes and values. Recent evidence suggests that a classic O(nt) dynamic programming solution for the Knapsack problem might be the fastest in the worst case. Our main results are algorithms with near-linear running times (in terms of the size of the knapsack and the number of items) for the Knapsack problem, if either the values or sizes of items are small integers. More specifically, if item sizes are integers bounded by smax, the running time of our algorithm is Õ((n+t)smax). If the item values are integers bounded by our algorithm runs in time Õ(n+tvmax). Best previously known running times were Õ(nt), Õ(n2smax), Õ(n2vmax) and Õ(n smax vmax). At the core of our algorithms lies a new technique, we call the prediction technique. Roughly speaking, the prediction technique enables us to compute the convolution of two vectors in time Õ(nemax) when the solution satisfies a monotonic structure and an approximation of the solution within an additive error of emax is available. Our results also improve the best known solutions for knapsack whose running times do not depend on t. 10:30 - 11:00 Coffee Break 11:00 - 11:25 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 - 11:55 Nima Anari — Planar Graph Perfect Matching is in NC Is perfect matching in NC? That is, is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of RNC matching algorithms. Within this question, the case of planar graphs has remained an enigma: On the one hand, counting the number of perfect matchings is far harder than finding one (the former is #P-complete and the latter is in P), and on the other, for planar graphs, counting has long been known to be in NC whereas finding one has resisted a solution. We give an NC algorithm for finding a perfect matching in a planar graph. Our algorithm uses the above-stated fact about counting matchings in a crucial way. Our main new idea is an NC algorithm for finding a face of the perfect matching polytope at which many new conditions, involving constraints of the polytope, are simultaneously satisfied. Several other ideas are also needed, such as finding a point in the interior of the minimum weight face of this polytope and finding a balanced tight odd set in NC. 12:00 - 12:25 Greg Bodwin — On the Structure of Unique Shortest Paths in Graphs Let P be a system of unique shortest paths through a graph with real edge weights. An obvious fact is that P is "consistent," meaning that no two of these paths can intersect each other, split apart, and then intersect again later. But is that all the guaranteed structure? Can any consistent path system be realized as unique shortest paths in some graph? Or are there more forbidden combinatorial intersection patterns out there to be found? We will characterize exactly which path systems can or can't be realized as unique shortest paths in some graph by giving a complete list of new forbidden intersection patterns. Our characterization theorem is based on a new connection between graph metrics and certain boundary operators used in some recent graph homology theories. This connection also leads to a principled topological understanding of some of the popular algebraic tricks currently used in the literature on shortest paths. 12:30 - 14:00 Lunch (provided) 14:00 - 15:30 Contributed talks 2 15:30 - 16:00 Coffee Break 16:00 - 16:55 Monika Henzinger — Survey on dynamic graph algorithm I will survey the main challenges in designing dynamic graph algorithms and the main developments in the last 5 years. Finally, I will explain how (in joint work with Pan Peng) we use techniques from property testing to develop new constant-time dynamic graph algorithms. 17:00 - 17:25 C. Seshadhri — Finding forbidden minors in sublinear time: an $n^{1/2 + o(1)}$-query one-sided tester for minor closed properties Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove eps*n edges from G to make it H-minor free (for some small constant eps > 0). We give a nearly n^{1/2} time algorithm that, with high probability, finds an H-minor in such a graph. As an application, consider a graph G that requires eps*n edge removals to make it planar. This result implies an algorithm, with the same running time, that produces a K_{3,3} or K_5 minor in G. No prior sublinear time bound was known for this problem. By the graph minor theorem, we get an analogous result for any minor-closed property. Up to n^{o(1)} factors, this result resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by lower bounds of Czumaj et al (RSA 2014). Joint work with Akash Kumar and Andrew Stolman. 17:30 - 17:55 Naveen Garg — Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time In the weighted flow-time problem on a single machine, we are given a set of n jobs, where each job has a processing requirement, a release date and a weight. The goal is to find a preemptive schedule which minimizes the sum of weighted flow-time of jobs, where the flow-time of a job is the difference between its completion time and its release date. In this talk I will present the first polynomial time constant approximation algorithm for this problem. 18:00 - 19:00 Poster session 2 19:00 - 20:00 Business meeting

## Accepted contributed presentations

Each contributed presentation will consist of a 4 minute talk, and on the same day, a poster presentation in the evening.

### Friday 14:00 - 15:30

 14:00 - 14:04 Yann Disser, Andreas Emil Feldmann, Max Klimm and Jochen Koenemann — Travelling on Graphs with Small Highway Dimension 14:05 - 14:09 Sandor Kisfaludi-Bak, Jesper Nederlof and Erik Jan van Leeuwen — Nearly ETH-Tight Algorithms for Planar Steiner Tree with Terminals on Few Faces 14:10 - 14:14 Ruben Becker, Federico Corò, Gianlorenzo D'Angelo and Hugo Gilbert — Balancing spreads of influence in a social network 14:15 - 14:19 Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni and Chris Schwiegelshohn — Oblivious Dimension Reduction for $k$-Means -- Beyond Subspaces and the Johnson-Lindenstrauss Lemma 14:20 - 14:24 Marcin Mucha, Karol Węgrzycki and Michal Wlodarczyk — A Subquadratic Approximation Scheme for Partition 14:25 - 14:29 Robert Krauthgamer, James Lee and Havana Rika — Flow-cut gaps and face covers in planar graphs 14:30 - 14:34 Rebecca Reiffenhäuser — An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem 14:35 - 14:39 Yuval Emek, Shay Kutten, Ron Lavi and William K. Moses Jr. — Deterministic Leader Election in Programmable Matter 14:40 - 14:44 Asaf Shapira and Lior Gishboliner — A generalized turan problem and its applications 14:45 - 14:49 Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemysław Uznański and Daniel Wolleb-Graf — Faster Algorithms for All-Pairs Bounded Min-Cuts 14:50 - 14:54 Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki and Eva Rotenberg — Decremental SPQR-trees for Planar Graphs 14:55 - 14:59 Martin Nägele and Rico Zenklusen — A New Contraction Technique with Applications to Congruency-Constrained Cuts 15:00 - 15:04 Amir Zandieh, Michael Kapralov and Ameya Velingker — Dimension-independent Sparse Fourier Transform 15:05 - 15:09 Karl Bringmann, Marvin Künnemann and André Nusser — Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance 15:10 - 15:14 Parinya Chalermsook, Andreas Schmid and Sumedha Uniyal — A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs 15:15 - 15:19 Magnús M. Halldórsson and Tigran Tonoyan — Plain SINR is Enough! 15:20 - 15:24 Janos Balogh, Cosmin Bonchis, Diana Dinis, Gabriel Istrate and Ioan Todinca — On the heapability of finite partial orders 15:25 - 15:29 Shimon Bitton, Yuval Emek and Shay Kutten — Efficient Jobs Dispatching in Emerging Clouds

### Saturday 14:00 - 15:30

 14:00 - 14:04 Bartlomiej Dudek and Pawel Gawrychowski — Computing Quartet Distance is Equivalent to Counting 4-Cycles 14:05 - 14:09 Peyman Afshani, Casper Benjamin Freksen, Lior Kamma and Kasper Green Larsen — Lower Bounds for Multiplication via Network Coding 14:10 - 14:14 Laszlo Kozma and Thatchaphol Saranurak — Smooth heaps and a dual view of self-adjusting data structures 14:15 - 14:19 Ran Ben Basat, Guy Even, Ken-Ichi Kawarabayashi and Gregory Schwartzman — Optimal Distributed Covering Algorithms 14:20 - 14:24 Kevin Yeo and Giuseppe Persiano — Lower Bounds for Differentially Private RAMs 14:25 - 14:29 Lingxiao Huang, Shaofeng H.-C. Jing, Jian Li and Xuan Wu — $arepsilon$-Coresets for Clustering (with Outliers) in Doubling Metrics 14:30 - 14:34 Mikkel Abrahamsen, Anna Adamaszek and Till Miltzow — The Art Gallery Problem is $\exists \mathbb{R}$-complete 14:35 - 14:39 Michael Bender, Ioana Bercea, Alex Conway, Guy Even, Tomer Even, Martin Farach-Colton and Rob Johnson — The Descent of Cuckoos, and Selection in Relation to Nests 14:40 - 14:44 Jaroslaw Byrka, Marcin Bienkowski, Marek Chrobak, Christian Coester, Łukasz Jeż and Elias Koustoupias — Better Bounds for Online Line Chasing 14:45 - 14:49 Jan van den Brand, Danupon Nanongkai and Thatchaphol Saranurak — Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds 14:50 - 14:54 Ilan Cohen and David Wajc — Randomized Online Matching in Regular Graphs via Online Dependent Rounding 14:55 - 14:59 Mohit Daga, Monika Henzinger, Danupon Nanongkai and Thatchaphol Saranurak — Distributed Edge Connectivity in Sublinear Time 15:00 - 15:04 Szymon Dudycz, Mateusz Lewandowski and Jan Marcinkowski — Tight Approximation Ratio for Minimum Maximal Matching 15:05 - 15:09 Diptarka Chakraborty, Lior Kamma and Kasper Green Larsen — Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication 15:10 - 15:14 Keerti Choudhary and Omer Gold — Diameter Spanners, Eccentricity Spanners, and Approximating Extremal Distances 15:15 - 15:19 Christian Coester and Elias Koutsoupias — The Online k-Taxi Problem 15:20 - 15:24 José Correa, Paul Duetting, Felix Fischer and Kevin Schewior — Prophet Inequalities for i.i.d. Random Variables from an Unknown Distribution 15:25 - 15:29 Keren Censor-Hillel, Ami Paz and Noam Ravid — The Sparsest Additive Spanner via Multiple Weighted BFS Trees

### Sunday 14:00 - 15:30

 14:00 - 14:04 Dominik Kempa and Tomasz Kociumaka — String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure 14:05 - 14:09 Amir Abboud, Robert Krauthgamer and Ohad Trabelsi — New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs 14:10 - 14:14 Rajesh Chitnis and Graham Cormode — Towards a Theory of Parameterized Streaming Algorithms 14:15 - 14:19 Thatchaphol Saranurak and Di Wang — Expander Decomposition and Pruning: Faster, Stronger, and Simpler 14:20 - 14:24 Dariusz Dereniowski, Stefan Tiegel, Przemysław Uznański and Daniel Wolleb-Graf — A Framework for Searching in Graphs in the Presence of Errors 14:25 - 14:29 Sarah Maria Morell, Alfonso Cevallos and Friedrich Eisenbrand — Diversity maximization in doubling metrics 14:30 - 14:34 Michael Kapralov, Navid Nouri, Aaron Sidford and Jakab Tardos — Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space 14:35 - 14:39 Yaniv Sadeh, Ori Rottenstreich, Arye Barkan, Yossi Kanizo and Haim Kaplan — Optimal Representations of a Traffic Distribution in Switch Memories 14:40 - 14:44 Karl Däubel — An Improved Upper Bound for the Ring Loading Problem 14:45 - 14:49 Yossi Azar, Ashish Chiplunkar, Shay Kutten and Noam Touitou — Set Cover and Vertex Cover with Delay 14:50 - 14:54 Jarosław Byrka, Piotr Skowron and Krzysztof Sornat — Proportional Approval Voting, Harmonic k-median, and Negative Association 14:55 - 14:59 Matthias Englert, Harald Räcke and Richard Stotz — Optimal Guarantees for Generalized Reordering Buffer Management 15:00 - 15:04 Karthik C. S. and Pasin Manurangsi — On Closest Pair: Monochromatic is as Hard as Bichromatic 15:05 - 15:09 Paweł Parys — Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time 15:10 - 15:14 Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl and Gerhard J. Woeginger — Dispersing obnoxious facilities on a graph 15:15 - 15:19 Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar and Yuval Peres — Testing Graph Clusterability: Algorithms and Lower Bounds 15:20 - 15:24 Vladimir Braverman, Shaofeng Jiang, Robert Krauthgamer and Xuan Wu — Coresets for Ordered Weighted Clustering 15:25 - 15:29 Danupon Nanongkai, Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai — Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme