University of Copenhagen, June 14-16, 2019


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&#337 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

Sunday, June 16

9:00 - 9:55
Sergei Vassilvitskii — Learning in Algorithms

Classic algorithm design focuses on optimizing worst case complexity, resulting in algorithms that perform well for any possible input. In many applications, however, the typical input is not just far from worst case, but has some predictable characteristics. We give an overview of recent results that incorporate machine learned predictions into algorithm design. Overall, these approaches improve the algorithms’ performance when predictions are correct, for instance, lowering competitive ratios of online algorithms, and space complexity of streaming algorithms; and nearly match the best known worst case performance bounds, when the predictions are wrong.

10:00 - 10:25
Rico Zenklusen — Improved Approximation for Tree Augmentation: Saving by Rewiring

The Tree Augmentation Problem (TAP) is a fundamental network design problem in which we are given a tree and a set of additional edges, also called links. The task is to find a link set of minimum size, whose addition to the tree leads to a 2-edge-connected graph. A long line of results on TAP culminated in the previously best known approximation guarantee of 1.5 by Kortsarz and Nutov, obtained through a combinatorial approach. More recently, this factor has been matched by an SDP-based approach by Cheriyan and Gao, and an LP-based (1.5+epsilon)-approximation has been obtained by Fiorini, Gross, Könemann, and Sanità. In this paper, we show that approximation factors below 1.5 can be achieved, by presenting a 1.458-approximation based on several new techniques. The main ingredient of our approach is a rewiring technique that is based on a stochastic version of a matching problem, and allows for saving links by replacing appropriate pairs of links by a single one.

10:30 - 11:00 Coffee Break
11:00 - 11:25
Robbie Weber — A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings

Appeared in STOC 2018; coauthored with Shayan Oveis Gharan and Anna Karlin. Search for paper

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

We study the parameterized complexity of approximating the k-Dominating Set (DomSet) problem where an integer k and a graph G on n vertices are given as input, and the goal is to find a dominating set of size at most F(k) k whenever the graph G has a dominating set of size k. When such an algorithm runs in time T(k) poly(n) (i.e., FPT-time) for some computable function T, it is said to be an F(k)-FPT-approximation algorithm for k-DomSet. We prove the following for every computable functions T,F and every constant ε>0:

  • Assuming W[1] ≠ FPT, there is no F(k)-FPT-approximation algorithm for k-DomSet.
  • Assuming the Exponential Time Hypothesis (ETH), there is no F(k)-approximation algorithm for k-DomSet that runs in T(k) no(k) time.
  • Assuming the Strong Exponential Time Hypothesis (SETH), for every integer k ≥ 2, there is no F(k)-approximation algorithm for k-DomSet that runs in T(k) n k−ε time.
  • Assuming the k-Sum Hypothesis, for every integer k ≥ 3, there is no F(k)-approximation algorithm for k-DomSet that runs in T(k) n⌈ k/2 ⌉ −ε time.

Our results are obtained by establishing a connection between communication complexity and hardness of approximation, generalizing the ideas from a recent breakthrough work of Abboud et al. [FOCS 2017]. Specifically, we show that to prove hardness of approximation of a certain parameterized variant of the label cover problem, it suffices to devise a specific protocol for a communication problem that depends on which hypothesis we rely on. Each of these communication problems turns out to be either a well studied problem or a variant of one; this allows us to easily apply known techniques to solve them.

This is a joint work with Karthik C. S. and Pasin Manurangsi

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

Many commonly used learning algorithms work by iteratively updating an intermediate solution using one or a few data points in each iteration. Analysis of differential privacy for such algorithms often involves ensuring privacy of each step and then reasoning about the cumulative privacy cost of the algorithm. This is enabled by composition theorems for differential privacy that allow releasing of all the intermediate results. In this work, we demonstrate that for contractive iterations, not releasing the intermediate results strongly amplifies the privacy guarantees.

We describe several applications of this new analysis technique to solving convex optimization problems via noisy stochastic gradient descent. For example, we demonstrate that a relatively small number of non-private data points from the same distribution can be used to close the gap between private and non-private convex optimization. In addition, we demonstrate that we can achieve guarantees similar to those obtainable using the privacy-amplification-by-sampling technique in several natural settings where that technique cannot be applied.

(Joint work with Vitaly Feldman, Ilya Mironov and Abhradeep Thakurta)

12:30 - 14:00 Lunch (provided)
14:00 - 15:30 Contributed talks 3
15:30 - 16:00 Coffee Break
16:00 - 16:55
Timothy Chan — 3SUM and Related Problems

In the well-known "3SUM" problem, we are given n numbers and want to find three numbers summing to 0. It is commonly believed that the problem does not have substantially subquadratic algorithms, and this conjecture has been used as a basis for many conditional hardness results in computational geometry and other areas. In 2014, Grønlund and Pettie made a breakthrough, giving the first subquadratic upper bound on the decision-tree complexity of the problem for real numbers, as well as the first slightly subquadratic algorithm. In this survey talk, I will sketch ideas leading to the latest algorithm with near n^2/log^2 n running time [SODA 2018], discuss related and 3SUM-hard problems, and also mention results on the integer case.

17:00 - 17:25
Sungjin Im — Online load balancing on related machines

In the load balancing problem, introduced by Graham in the 1960s (SIAM J. of Appl. Math. 1966, 1969), jobs arriving online have to be assigned to machines so to minimize an objective defined on machine loads. A long line of work has addressed this problem for both the makespan norm and arbitrary ℓq-norms of machine loads. Recent literature (e.g., Azar et al., STOC 2013; Im et al., FOCS 2015) has further expanded the scope of this problem to vector loads, to capture jobs with multi-dimensional resource requirements in applications such as data centers. In this work, we completely resolve the job scheduling problem for both scalar and vector jobs on related machines, i.e., where each machine has a given speed and the time taken to process a job is inversely proportional to the speed of the machine it is assigned on. We show the following results. For scalar scheduling, we give a constant competitive algorithm for optimizing any ℓq-norm for related machines. The only previously known result was for the makespan norm. For vector scheduling, there are two natural variants for vector scheduling, depending on whether the speed of a machine is dimension-dependent or not. We show a sharp contrast between these two variants, proving that they are respectively equivalent to unrelated machines and identical machines for the makespan norm. We also extend these results to arbitrary ℓq-norms of the machine loads. No previous results were known for vector scheduling on related machines.

This is a joint-work with Nathaniel Kell, Debmalya Panigrahi, and Maryam Shadloo.

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

We derive linear decision trees for a variety of decision problems in combinatorics and discrete geometry. For example, for any k, we construct linear decision trees that solve the k-SUM problem on n elements using O(nk log n) linear queries. Moreover, the queries we use are comparison queries, which compare the sums of two k-subsets; when viewed as linear queries, comparison queries are 2k-sparse and have only {−1,+1} coefficients. We give similar constructions for sorting sumsets A+B and for solving the SUBSET-SUM problem, both with optimal number of queries, up to poly-logarithmic terms.

These derivations hinge on a combinatorial parameter called the inference dimension, which characterizes query complexity in interactive learning.

In the talk we will give a gentle introduction to interactive learning and explain its natural connection to the above mentioned decision problems in combinatorics and geometry.

18:00 - 19:00 Poster session 3

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