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 problemThe 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 DegreeIn 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 NPThere 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 MultiplicationWe 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 graphsThe 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 analysisOne 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 KernelsGiven a kernel function k(.,.) and a dataset P ⊂ ℝ^{d} , the kernel density function of P at a point x ∈ ℝ^{d} is equal to KDF_{P}(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 KDF_{P}(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 KDF_{P}(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 DecompositionsWe 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:
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 timeAppeared 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 systemsThe 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 predictionIt 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. 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 s_{max}, the running time of our algorithm is Õ((n+t)s_{max}). If the item values are integers bounded by our algorithm runs in time Õ(n+tv_{max}). Best previously known running times were Õ(nt), Õ(n^{2}s_{max}), Õ(n^{2}v_{max}) and Õ(n s_{max} v_{max}). 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 Õ(ne_{max}) when the solution satisfies a monotonic structure and an approximation of the solution within an additive error of e_{max} 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 regularizationAppeared 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 NCIs 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 GraphsLet 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 algorithmI 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 propertiesLet 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 timeIn 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 AlgorithmsClassic 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 RewiringThe 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 MatchingsAppeared 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 setWe 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:
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 IterationMany 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 ProblemsIn 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 machinesIn 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 problemsWe 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 |