@inproceedings{10055,
  abstract     = {Repeated idempotent elements are commonly used to characterise iterable behaviours in abstract models of computation. Therefore, given a monoid M, it is natural to ask how long a sequence of elements of M needs to be to ensure the presence of consecutive idempotent factors. This question is formalised through the notion of the Ramsey function R_M associated to M, obtained by mapping every k ∈ ℕ to the minimal integer R_M(k) such that every word u ∈ M^* of length R_M(k) contains k consecutive non-empty factors that correspond to the same idempotent element of M. In this work, we study the behaviour of the Ramsey function R_M by investigating the regular 𝒟-length of M, defined as the largest size L(M) of a submonoid of M isomorphic to the set of natural numbers {1,2, …, L(M)} equipped with the max operation. We show that the regular 𝒟-length of M determines the degree of R_M, by proving that k^L(M) ≤ R_M(k) ≤ (k|M|⁴)^L(M). To allow applications of this result, we provide the value of the regular 𝒟-length of diverse monoids. In particular, we prove that the full monoid of n × n Boolean matrices, which is used to express transition monoids of non-deterministic automata, has a regular 𝒟-length of (n²+n+2)/2.},
  author       = {Jecker, Ismael R},
  booktitle    = {38th International Symposium on Theoretical Aspects of Computer Science},
  isbn         = {978-3-9597-7180-1},
  issn         = {1868-8969},
  location     = {Saarbrücken, Germany},
  publisher    = {Schloss Dagstuhl - Leibniz Zentrum für Informatik},
  title        = {{A Ramsey theorem for finite monoids}},
  doi          = {10.4230/LIPIcs.STACS.2021.44},
  volume       = {187},
  year         = {2021},
}

@inproceedings{10072,
  abstract     = {The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthrough paper of Moser and Tardos and follow-up works revealed that the LLL has intimate connections with a class of stochastic local search algorithms for finding such desirable objects. In particular, it can be seen as a sufficient condition for this type of algorithms to converge fast. Besides conditions for existence of and fast convergence to desirable objects, one may naturally ask further questions regarding properties of these algorithms. For instance, "are they parallelizable?", "how many solutions can they output?", "what is the expected "weight" of a solution?", etc. These questions and more have been answered for a class of LLL-inspired algorithms called commutative. In this paper we introduce a new, very natural and more general notion of commutativity (essentially matrix commutativity) which allows us to show a number of new refined properties of LLL-inspired local search algorithms with significantly simpler proofs.},
  author       = {Harris, David G. and Iliopoulos, Fotis and Kolmogorov, Vladimir},
  booktitle    = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques},
  isbn         = {978-3-9597-7207-5},
  issn         = {1868-8969},
  location     = {Virtual},
  publisher    = {Schloss Dagstuhl - Leibniz Zentrum für Informatik},
  title        = {{A new notion of commutativity for the algorithmic Lovász Local Lemma}},
  doi          = {10.4230/LIPIcs.APPROX/RANDOM.2021.31},
  volume       = {207},
  year         = {2021},
}

@inproceedings{10075,
  abstract     = {We study the expressiveness and succinctness of good-for-games pushdown automata (GFG-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved based on the run constructed so far, but independently of the remainder of the input word. We prove that GFG-PDA recognise more languages than deterministic PDA (DPDA) but not all context-free languages (CFL). This class is orthogonal to unambiguous CFL. We further show that GFG-PDA can be exponentially more succinct than DPDA, while PDA can be double-exponentially more succinct than GFG-PDA. We also study GFGness in visibly pushdown automata (VPA), which enjoy better closure properties than PDA, and for which we show GFGness to be ExpTime-complete. GFG-VPA can be exponentially more succinct than deterministic VPA, while VPA can be exponentially more succinct than GFG-VPA. Both of these lower bounds are tight. Finally, we study the complexity of resolving nondeterminism in GFG-PDA. Every GFG-PDA has a positional resolver, a function that resolves nondeterminism and that is only dependant on the current configuration. Pushdown transducers are sufficient to implement the resolvers of GFG-VPA, but not those of GFG-PDA. GFG-PDA with finite-state resolvers are determinisable.},
  author       = {Guha, Shibashis and Jecker, Ismael R and Lehtinen, Karoliina and Zimmermann, Martin},
  booktitle    = {46th International Symposium on Mathematical Foundations of Computer Science},
  isbn         = {978-3-9597-7201-3},
  issn         = {1868-8969},
  location     = {Tallinn, Estonia},
  publisher    = {Schloss Dagstuhl - Leibniz Zentrum für Informatik},
  title        = {{A bit of nondeterminism makes pushdown automata expressive and succinct}},
  doi          = {10.4230/LIPIcs.MFCS.2021.53},
  volume       = {202},
  year         = {2021},
}

@inproceedings{10216,
  abstract     = {This paper reports a new concurrent graph data structure that supports updates of both edges and vertices and queries: Breadth-first search, Single-source shortest-path, and Betweenness centrality. The operations are provably linearizable and non-blocking.},
  author       = {Chatterjee, Bapi and Peri, Sathya and Sa, Muktikanta},
  booktitle    = {35th International Symposium on Distributed Computing},
  isbn         = {9-783-9597-7210-5},
  issn         = {1868-8969},
  location     = {Freiburg, Germany},
  publisher    = {Schloss Dagstuhl - Leibniz Zentrum für Informatik},
  title        = {{Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds}},
  doi          = {10.4230/LIPIcs.DISC.2021.52},
  volume       = {209},
  year         = {2021},
}

@inproceedings{10217,
  abstract     = {This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registers, for both deterministic and randomized obstruction-free algorithms. The approach extends to lower bounds for deterministic and randomized obstruction-free algorithms using multi-writer registers under bounded write concurrency, showing a trade-off between the solo step complexity of a leader election algorithm, and the worst-case number of stalls incurred by a processor in an execution.},
  author       = {Alistarh, Dan-Adrian and Gelashvili, Rati and Nadiradze, Giorgi},
  booktitle    = {35th International Symposium on Distributed Computing},
  isbn         = {9-783-9597-7210-5},
  issn         = {1868-8969},
  location     = {Freiburg, Germany},
  publisher    = {Schloss Dagstuhl - Leibniz Zentrum für Informatik},
  title        = {{Lower bounds for shared-memory leader election under bounded write contention}},
  doi          = {10.4230/LIPIcs.DISC.2021.4},
  volume       = {209},
  year         = {2021},
}

@inproceedings{10218,
  abstract     = {Let G be a graph on n nodes. In the stochastic population protocol model, a collection of n indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other’s states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when G is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in n polylog n pairwise interactions, with high probability, using at most polylog n states per node. In this work, we consider the more general setting where G is an arbitrary graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As an example, this implies that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties.},
  author       = {Alistarh, Dan-Adrian and Gelashvili, Rati and Rybicki, Joel},
  booktitle    = {35th International Symposium on Distributed Computing},
  isbn         = {9-783-9597-7210-5},
  issn         = {1868-8969},
  location     = {Freiburg, Germany},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Brief announcement: Fast graphical population protocols}},
  doi          = {10.4230/LIPIcs.DISC.2021.43},
  volume       = {209},
  year         = {2021},
}

@inproceedings{10219,
  abstract     = {We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n).},
  author       = {Korhonen, Janne and Paz, Ami and Rybicki, Joel and Schmid, Stefan and Suomela, Jukka},
  booktitle    = {35th International Symposium on Distributed Computing},
  isbn         = {9-783-9597-7210-5},
  issn         = {1868-8969},
  location     = {Freiburg, Germany},
  publisher    = {Schloss Dagstuhl - Leibniz Zentrum für Informatik},
  title        = {{Brief announcement: Sinkless orientation is hard also in the supported LOCAL model}},
  doi          = {10.4230/LIPIcs.DISC.2021.58},
  volume       = {209},
  year         = {2021},
}

@inproceedings{10629,
  abstract     = {Product graphs arise naturally in formal verification and program analysis. For example, the analysis of two concurrent threads requires the product of two component control-flow graphs, and for language inclusion of deterministic automata the product of two automata is constructed. In many cases, the component graphs have constant treewidth, e.g., when the input contains control-flow graphs of programs. We consider the algorithmic analysis of products of two constant-treewidth graphs with respect to three classic specification languages, namely, (a) algebraic properties, (b) mean-payoff properties, and (c) initial credit for energy properties.
Our main contributions are as follows. Consider a graph G that is the product of two constant-treewidth graphs of size n each. First, given an idempotent semiring, we present an algorithm that computes the semiring transitive closure of G in time Õ(n⁴). Since the output has size Θ(n⁴), our algorithm is optimal (up to polylog factors). Second, given a mean-payoff objective, we present an O(n³)-time algorithm for deciding whether the value of a starting state is non-negative, improving the previously known O(n⁴) bound. Third, given an initial credit for energy objective, we present an O(n⁵)-time algorithm for computing the minimum initial credit for all nodes of G, improving the previously known O(n⁸) bound. At the heart of our approach lies an algorithm for the efficient construction of strongly-balanced tree decompositions of constant-treewidth graphs. Given a constant-treewidth graph G' of n nodes and a positive integer λ, our algorithm constructs a binary tree decomposition of G' of width O(λ) with the property that the size of each subtree decreases geometrically with rate (1/2 + 2^{-λ}).},
  author       = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas},
  booktitle    = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  isbn         = {978-3-9597-7215-0},
  issn         = {1868-8969},
  location     = {Virtual},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Quantitative verification on product graphs of small treewidth}},
  doi          = {10.4230/LIPIcs.FSTTCS.2021.42},
  volume       = {213},
  year         = {2021},
}

@inproceedings{10630,
  abstract     = {In the Intersection Non-emptiness problem, we are given a list of finite automata A_1, A_2,… , A_m over a common alphabet Σ as input, and the goal is to determine whether some string w ∈ Σ^* lies in the intersection of the languages accepted by the automata in the list. We analyze the complexity of the Intersection Non-emptiness problem under the promise that all input automata accept a language in some level of the dot-depth hierarchy, or some level of the Straubing-Thérien hierarchy. Automata accepting languages from the lowest levels of these hierarchies arise naturally in the context of model checking. We identify a dichotomy in the dot-depth hierarchy by showing that the problem is already NP-complete when all input automata accept languages of the levels B_0 or B_{1/2} and already PSPACE-hard when all automata accept a language from the level B_1. Conversely, we identify a tetrachotomy in the Straubing-Thérien hierarchy. More precisely, we show that the problem is in AC^0 when restricted to level L_0; complete for L or NL, depending on the input representation, when restricted to languages in the level L_{1/2}; NP-complete when the input is given as DFAs accepting a language in L_1 or L_{3/2}; and finally, PSPACE-complete when the input automata accept languages in level L_2 or higher. Moreover, we show that the proof technique used to show containment in NP for DFAs accepting languages in L_1 or L_{3/2} does not generalize to the context of NFAs. To prove this, we identify a family of languages that provide an exponential separation between the state complexity of general NFAs and that of partially ordered NFAs. To the best of our knowledge, this is the first superpolynomial separation between these two models of computation.},
  author       = {Arrighi, Emmanuel and Fernau, Henning and Hoffmann, Stefan and Holzer, Markus and Jecker, Ismael R and De Oliveira Oliveira, Mateus and Wolf, Petra},
  booktitle    = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  isbn         = {978-3-9597-7215-0},
  issn         = {1868-8969},
  location     = {Virtual},
  publisher    = {Schloss Dagstuhl - Leibniz Zentrum für Informatik},
  title        = {{On the complexity of intersection non-emptiness for star-free language classes}},
  doi          = {10.4230/LIPIcs.FSTTCS.2021.34},
  volume       = {213},
  year         = {2021},
}

@inproceedings{9441,
  abstract     = {Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation M̂ based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂ is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M̂ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. },
  author       = {Boissonnat, Jean-Daniel and Kachanovich, Siargey and Wintraecken, Mathijs},
  booktitle    = {37th International Symposium on Computational Geometry (SoCG 2021)},
  isbn         = {978-3-95977-184-9},
  issn         = {1868-8969},
  location     = {Virtual},
  pages        = {17:1--17:16},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations}},
  doi          = {10.4230/LIPIcs.SoCG.2021.17},
  volume       = {189},
  year         = {2021},
}

@inproceedings{11814,
  abstract     = {Differentially private algorithms protect individuals in data analysis scenarios by ensuring that there is only a weak correlation between the existence of the user in the data and the result of the analysis. Dynamic graph algorithms maintain the solution to a problem (e.g., a matching) on an evolving input, i.e., a graph where nodes or edges are inserted or deleted over time. They output the value of the solution after each update operation, i.e., continuously. We study (event-level and user-level) differentially private algorithms for graph problems under continual observation, i.e., differentially private dynamic graph algorithms. We present event-level private algorithms for partially dynamic counting-based problems such as triangle count that improve the additive error by a polynomial factor (in the length T of the update sequence) on the state of the art, resulting in the first algorithms with additive error polylogarithmic in T.
We also give ε-differentially private and partially dynamic algorithms for minimum spanning tree, minimum cut, densest subgraph, and maximum matching. The additive error of our improved MST algorithm is O(W log^{3/2}T / ε), where W is the maximum weight of any edge, which, as we show, is tight up to a (√{log T} / ε)-factor. For the other problems, we present a partially-dynamic algorithm with multiplicative error (1+β) for any constant β > 0 and additive error O(W log(nW) log(T) / (ε β)). Finally, we show that the additive error for a broad class of dynamic graph algorithms with user-level privacy must be linear in the value of the output solution’s range.},
  author       = {Fichtenberger, Hendrik and Henzinger, Monika H and Ost, Wolfgang},
  booktitle    = {29th Annual European Symposium on Algorithms},
  isbn         = {9783959772044},
  issn         = {1868-8969},
  location     = {Lisbon, Portual},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Differentially private algorithms for graphs under continual observation}},
  doi          = {10.4230/LIPIcs.ESA.2021.42},
  volume       = {204},
  year         = {2021},
}

@inproceedings{8725,
  abstract     = {The design and implementation of efficient concurrent data structures have
seen significant attention. However, most of this work has focused on
concurrent data structures providing good \emph{worst-case} guarantees. In real
workloads, objects are often accessed at different rates, since access
distributions may be non-uniform. Efficient distribution-adaptive data
structures are known in the sequential case, e.g. the splay-trees; however,
they often are hard to translate efficiently in the concurrent case.
  In this paper, we investigate distribution-adaptive concurrent data
structures and propose a new design called the splay-list. At a high level, the
splay-list is similar to a standard skip-list, with the key distinction that
the height of each element adapts dynamically to its access rate: popular
elements ``move up,'' whereas rarely-accessed elements decrease in height. We
show that the splay-list provides order-optimal amortized complexity bounds for
a subset of operations while being amenable to efficient concurrent
implementation. Experimental results show that the splay-list can leverage
distribution-adaptivity to improve on the performance of classic concurrent
designs, and can outperform the only previously-known distribution-adaptive
design in certain settings.},
  author       = {Aksenov, Vitaly and Alistarh, Dan-Adrian and Drozdova, Alexandra and Mohtashami, Amirkeivan},
  booktitle    = {34th International Symposium on Distributed Computing},
  isbn         = {9783959771689},
  issn         = {1868-8969},
  location     = {Freiburg, Germany},
  pages        = {3:1--3:18},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{The splay-list: A distribution-adaptive concurrent skip-list}},
  doi          = {10.4230/LIPIcs.DISC.2020.3},
  volume       = {179},
  year         = {2020},
}

@inproceedings{7348,
  abstract     = {The monitoring of event frequencies can be used to recognize behavioral anomalies, to identify trends, and to deduce or discard hypotheses about the underlying system. For example, the performance of a web server may be monitored based on the ratio of the total count of requests from the least and most active clients. Exact frequency monitoring, however, can be prohibitively expensive; in the above example it would require as many counters as there are clients. In this paper, we propose the efficient probabilistic monitoring of common frequency properties, including the mode (i.e., the most common event) and the median of an event sequence. We define a logic to express composite frequency properties as a combination of atomic frequency properties. Our main contribution is an algorithm that, under suitable probabilistic assumptions, can be used to monitor these important frequency properties with four counters, independent of the number of different events. Our algorithm samples longer and longer subwords of an infinite event sequence. We prove the almost-sure convergence of our algorithm by generalizing ergodic theory from increasing-length prefixes to increasing-length subwords of an infinite sequence. A similar algorithm could be used to learn a connected Markov chain of a given structure from observing its outputs, to arbitrary precision, for a given confidence. },
  author       = {Ferrere, Thomas and Henzinger, Thomas A and Kragl, Bernhard},
  booktitle    = {28th EACSL Annual Conference on Computer Science Logic},
  isbn         = {9783959771320},
  issn         = {1868-8969},
  location     = {Barcelona, Spain},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Monitoring event frequencies}},
  doi          = {10.4230/LIPIcs.CSL.2020.20},
  volume       = {152},
  year         = {2020},
}

@inproceedings{7952,
  abstract     = {Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f: ℝ^d → ℝ^(d-n). A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine triangulation 𝒯. This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary. },
  author       = {Boissonnat, Jean-Daniel and Wintraecken, Mathijs},
  booktitle    = {36th International Symposium on Computational Geometry},
  isbn         = {978-3-95977-143-6},
  issn         = {1868-8969},
  location     = {Zürich, Switzerland},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{The topological correctness of PL-approximations of isomanifolds}},
  doi          = {10.4230/LIPIcs.SoCG.2020.20},
  volume       = {164},
  year         = {2020},
}

@inproceedings{11816,
  abstract     = {In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances.},
  author       = {Henzinger, Monika H and Shahbaz, Khan and Paul, Richard and Schulz, Christian},
  booktitle    = {8th Annual European Symposium on Algorithms},
  isbn         = {9783959771627},
  issn         = {1868-8969},
  location     = {Pisa, Italy},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Dynamic matching algorithms in practice}},
  doi          = {10.4230/LIPIcs.ESA.2020.58},
  volume       = {173},
  year         = {2020},
}

@inproceedings{11818,
  abstract     = {With input sizes becoming massive, coresets - small yet representative summary of the input - are relevant more than ever. A weighted set C_w that is a subset of the input is an ε-coreset if the cost of any feasible solution S with respect to C_w is within [1±ε] of the cost of S with respect to the original input. We give a very general technique to compute coresets in the fully-dynamic setting where input points can be added or deleted. Given a static (i.e., not dynamic) ε-coreset-construction algorithm that runs in time t(n, ε, λ) and computes a coreset of size s(n, ε, λ), where n is the number of input points and 1-λ is the success probability, we give a fully-dynamic algorithm that computes an ε-coreset with worst-case update time O((log n) ⋅ t(s(n, ε/log n, λ/n), ε/log n, λ/n)) (this bound is stated informally), where the success probability is 1-λ. Our technique is a fully-dynamic analog of the merge-and-reduce technique, which is due to Har-Peled and Mazumdar [Har-Peled and Mazumdar, 2004] and is based on a technique of Bentley and Saxe [Jon Louis Bentley and James B. Saxe, 1980], that applies to the insertion-only setting where points can only be added. Although, our space usage is O(n), our technique works in the presence of an adaptive adversary, and we show that Ω(n) space is required when adversary is adaptive.
As a concrete implication of our technique, using the result of Braverman et al. [{Braverman} et al., 2016], we get fully-dynamic ε-coreset-construction algorithms for k-median and k-means with worst-case update time O(ε^{-2} k² log⁵ n log³ k) and coreset size O(ε^{-2} k log n log² k) ignoring log log n and log(1/ε) factors and assuming that ε = Ω(1/poly(n)) and λ = Ω(1/poly(n)) (which are very weak assumptions made only to make these bounds easy to parse). This results in the first fully-dynamic constant-approximation algorithms for k-median and k-means with update times O(poly(k, log n, ε^{-1})). Specifically, the dependence on k is only quadratic, and the bounds are worst-case. The best previous bound for both problems was amortized O(nlog n) by Cohen-Addad et al. [Cohen-Addad et al., 2019] via randomized O(1)-coresets in O(n) space.
We also show that under the OMv conjecture [Monika Henzinger et al., 2015], a fully-dynamic (4 - δ)-approximation algorithm for k-means must either have an amortized update time of Ω(k^{1-γ}) or amortized query time of Ω(k^{2 - γ}), where γ > 0 is a constant.},
  author       = {Henzinger, Monika H and Kale, Sagar},
  booktitle    = {28th Annual European Symposium on Algorithms},
  isbn         = {9783959771627},
  issn         = {1868-8969},
  location     = {Pisa, Italy},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Fully-dynamic coresets}},
  doi          = {10.4230/LIPIcs.ESA.2020.57},
  volume       = {173},
  year         = {2020},
}

@inproceedings{11819,
  abstract     = {We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.},
  author       = {Henzinger, Monika H and Noe, Alexander and Schulz, Christian and Strash, Darren},
  booktitle    = {28th Annual European Symposium on Algorithms},
  isbn         = {9783959771627},
  issn         = {1868-8969},
  location     = {Pisa, Italy},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Finding all global minimum cuts in practice}},
  doi          = {10.4230/LIPIcs.ESA.2020.59},
  volume       = {173},
  year         = {2020},
}

@inproceedings{11822,
  abstract     = {The fully dynamic transitive closure problem asks to maintain reachability information in a directed graph between arbitrary pairs of vertices, while the graph undergoes a sequence of edge insertions and deletions. The problem has been thoroughly investigated in theory and many specialized algorithms for solving it have been proposed in the last decades. In two large studies [Frigioni ea, 2001; Krommidas and Zaroliagis, 2008], a number of these algorithms have been evaluated experimentally against simple, static algorithms for graph traversal, showing the competitiveness and even superiority of the simple algorithms in practice, except for very dense random graphs or very high ratios of queries. A major drawback of those studies is that only small and mostly randomly generated graphs are considered.
In this paper, we engineer new algorithms to maintain all-pairs reachability information which are simple and space-efficient. Moreover, we perform an extensive experimental evaluation on both generated and real-world instances that are several orders of magnitude larger than those in the previous studies. Our results indicate that our new algorithms outperform all state-of-the-art algorithms on all types of input considerably in practice.},
  author       = {Hanauer, Kathrin and Henzinger, Monika H and Schulz, Christian},
  booktitle    = {18th International Symposium on Experimental Algorithms},
  isbn         = {9783959771481},
  issn         = {1868-8969},
  location     = {Pisa, Italy},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Faster fully dynamic transitive closure in practice}},
  doi          = {10.4230/LIPIcs.SEA.2020.14},
  volume       = {160},
  year         = {2020},
}

@inproceedings{11824,
  abstract     = {Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there are approximation algorithms known in the offline setting. These graph classes include interval graphs and geometric intersection graphs, where vertices correspond to intervals/geometric objects and an edge indicates that the two corresponding objects intersect.
We present dynamic approximation algorithms for independent set of intervals, hypercubes and hyperrectangles in d dimensions. They work in the fully dynamic model where each update inserts or deletes a geometric object. All our algorithms are deterministic and have worst-case update times that are polylogarithmic for constant d and ε>0, assuming that the coordinates of all input objects are in [0, N]^d and each of their edges has length at least 1. We obtain the following results:
- For weighted intervals, we maintain a (1+ε)-approximate solution.
- For d-dimensional hypercubes we maintain a (1+ε)2^d-approximate solution in the unweighted case and a O(2^d)-approximate solution in the weighted case. Also, we show that for maintaining an unweighted (1+ε)-approximate solution one needs polynomial update time for d ≥ 2 if the ETH holds.
- For weighted d-dimensional hyperrectangles we present a dynamic algorithm with approximation ratio (1+ε)log^{d-1}N.},
  author       = {Henzinger, Monika H and Neumann, Stefan and Wiese, Andreas},
  booktitle    = {36th International Symposium on Computational Geometry},
  isbn         = {9783959771436},
  issn         = {1868-8969},
  location     = {Zurich, Switzerland},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles}},
  doi          = {10.4230/LIPIcs.SoCG.2020.51},
  volume       = {164},
  year         = {2020},
}

@inproceedings{11825,
  abstract     = {We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time per update that maintains a proper (Δ+1)-vertex coloring of a graph with maximum degree at most Δ. This improves upon the previous O(log Δ)-time algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based on assigning random ranks to vertices and does not need to maintain a hierarchical graph decomposition. We show that our result does not only have optimal running time, but is also optimal in the sense that already deciding whether a Δ-coloring exists in a dynamically changing graph with maximum degree at most Δ takes Ω(log n) time per operation.},
  author       = {Henzinger, Monika H and Peng, Pan},
  booktitle    = {37th International Symposium on Theoretical Aspects of Computer Science},
  isbn         = {9783959771405},
  issn         = {1868-8969},
  location     = {Montpellier, France},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Constant-time dynamic (Δ+1)-coloring}},
  doi          = {10.4230/LIPIcs.STACS.2020.53},
  volume       = {154},
  year         = {2020},
}