33 Search Results for "Rozhoň, Václav"

Document
DOI: 10.4230/LIPIcs.STACS.2026.71
Broadcast in Almost Mixing Time

Authors: Anton Paramonov and Roger Wattenhofer

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study the problem of broadcasting multiple messages in the CONGEST model. In this problem, a dedicated source node s possesses a set M of messages with every message of size O(log n) where n is the total number of nodes. The objective is to ensure that every node in the network learns all messages in M. The execution of an algorithm progresses in rounds, and we focus on optimizing the round complexity of broadcasting multiple messages. Our primary contribution is a randomized algorithm for networks with expander topology. The algorithm succeeds with high probability and achieves a round complexity that is optimal up to a factor of the network’s mixing time and polylogarithmic terms. It leverages a multi-COBRA primitive, which uses multiple branching random walks running in parallel. A crucial aspect of our method is the use of these branching random walks to construct an optimal (up to a polylogarithmic factor) tree packing of a random graph, which is then used for efficient broadcasting. We also prove the problem to be NP-hard in a centralized setting and provide insights into why lower bounds that can be matched in expanders, namely graph diameter and |M|/minCut, cannot be tight in general graphs.
Cite as

Anton Paramonov and Roger Wattenhofer. Broadcast in Almost Mixing Time. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 71:1-71:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{paramonov_et_al:LIPIcs.STACS.2026.71,
  author =	{Paramonov, Anton and Wattenhofer, Roger},
  title =	{{Broadcast in Almost Mixing Time}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{71:1--71:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.71},
  URN =		{urn:nbn:de:0030-drops-255603},
  doi =		{10.4230/LIPIcs.STACS.2026.71},
  annote =	{Keywords: Distributed algorithms, Expander Graphs, Random graphs, Broadcast, Branching random walks, Tree packing, CONGEST model}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.19
Orientation Does Not Help with 3-Coloring a Grid in Online-LOCAL

Authors: Thomas Boudier, Filippo Casagrande, Avinandan Das, Massimo Equi, Henrik Lievonen, Augusto Modanese, and Ronja Stimpert

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the only problem we know of where the global memory of the online-LOCAL model has an advantage over SLOCAL is 3-coloring bipartite graphs. Recently, Chang et al. [PODC 2024] showed that even in grids, 3-coloring requires Ω(log n) locality in deterministic online-LOCAL. This result was subsequently extended by Akbari et al. [STOC 2025] to also hold in randomized online-LOCAL. However, both proofs heavily rely on the assumption that the algorithm does not have access to the orientation of the underlying grid. In this paper, we show how to lift this requirement and obtain the same lower bound (against either model) even when the algorithm is explicitly given a globally consistent orientation of the grid.
Cite as

Thomas Boudier, Filippo Casagrande, Avinandan Das, Massimo Equi, Henrik Lievonen, Augusto Modanese, and Ronja Stimpert. Orientation Does Not Help with 3-Coloring a Grid in Online-LOCAL. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{boudier_et_al:LIPIcs.OPODIS.2025.19,
  author =	{Boudier, Thomas and Casagrande, Filippo and Das, Avinandan and Equi, Massimo and Lievonen, Henrik and Modanese, Augusto and Stimpert, Ronja},
  title =	{{Orientation Does Not Help with 3-Coloring a Grid in Online-LOCAL}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.19},
  URN =		{urn:nbn:de:0030-drops-251925},
  doi =		{10.4230/LIPIcs.OPODIS.2025.19},
  annote =	{Keywords: coloring, locally checkable labeling problems, online algorithms}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.25
On the Complexity of Distributed Edge Coloring and Orientation Problems

Authors: Sebastian Brandt, Fabian Kuhn, and Zahra Parsaeian

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
Understanding the role of randomness when solving locally checkable labeling (LCL) problems in the LOCAL model has been one of the top priorities in the research on distributed graph algorithms in recent years. For LCL problems in bounded-degree graphs, it is known that randomness cannot help more than polynomially, except in one case: if the deterministic complexity of an LCL problem is in Ω(log n) and its randomized complexity is in o(log n), then the randomized complexity is guaranteed to be O(poly(log log n)) and it is even known to be O(log log n) in bounded-degree trees. However, the fundamental question of which problems with a deterministic complexity of Ω(log n) can be solved exponentially faster using randomization still remains wide open. We make a step towards answering this question by studying a simple, but natural class of LCL problems: so-called degree splitting problems. These problems come in two varieties: coloring problems where the edges of a graph have to be colored with 2 colors and orientation problems where each edge needs to be oriented. For an exact classification, it is most natural to consider the Δ-regular case (for Δ = O(1)), where we obtain the following results. - We exactly characterize the complexity of problems where the edges need to be colored with two colors, say red and blue. We show that for every y ∈ {0,… ,Δ-1}, the problem of red-blue coloring the edges such that every node of degree Δ has either y or y+1 red edges has randomized complexity O(log log n) in general graphs of maximum degree Δ. Any other problem, i.e., any problem that does not allow two consecutive red degrees, is already known to have randomized complexity Ω(log n) even in Δ-regular trees. We note that a set of edges F such that every node has either y or y+1 incident edges in F is also known as a {y,y+1}-factor of a graph. - For edge orientations, we show that for any two r₁ and r₂ such that r₁,r₂ ≤ Δ/2 and r₁+r₂ ≥ Δ/2, there are randomized algorithms with round complexities O(log log n) in trees and Õ(log⁴log n) in general graphs to compute an edge orientation such that all nodes have outdegree r₁ ± O(√{ΔlogΔ}) or Δ-r₂ ± O(√{ΔlogΔ}). Further, there exists a constant c > 0 such that for any 0 ≤ r₁+r₂ ≤ Δ/2, the problem of computing an edge orientation in which all outdegrees are either at most r₁-c⋅ √{Δ} or at least Δ-r₂+c⋅√{Δ} has randomized complexity Ω(log n) even in Δ-regular trees. While our results are cleanest to state for the Δ-regular case, all our algorithms naturally generalize to nodes of any degree d < Δ in general graphs of maximum degree Δ. All our algorithms also naturally generalize to the unbounded degree case and they then have a randomized complexity of Õ(Δ) ⋅ log log n (resp. Õ(Δ ⋅log⁴log n) for orienting general graphs).
Cite as

Sebastian Brandt, Fabian Kuhn, and Zahra Parsaeian. On the Complexity of Distributed Edge Coloring and Orientation Problems. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brandt_et_al:LIPIcs.OPODIS.2025.25,
  author =	{Brandt, Sebastian and Kuhn, Fabian and Parsaeian, Zahra},
  title =	{{On the Complexity of Distributed Edge Coloring and Orientation Problems}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{25:1--25:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.25},
  URN =		{urn:nbn:de:0030-drops-251982},
  doi =		{10.4230/LIPIcs.OPODIS.2025.25},
  annote =	{Keywords: LCL problems, binary labeling problems, degree splitting}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.23
Distributed (Δ+1)-Coloring in Graphs of Bounded Neighborhood Independence

Authors: Marc Fuchs and Fabian Kuhn

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
The distributed coloring problem is arguably one of the key problems studied in the area of distributed graph algorithms. The most standard variant of the problem asks for a proper vertex coloring of a graph with Δ+1 colors, where Δ is the maximum degree of the graph. Despite an immense amount of work on distributed coloring problems in the distributed setting, determining the deterministic complexity of (Δ+1)-coloring in the standard message passing model remains one of the most important open questions of the area. In the LOCAL model, it is known that (Δ+1)-coloring requires Ω(log^* n) rounds even in paths and rings (i.e., when Δ = 2). For general graphs, the problem is known to be solvable in Õ(log^{5/3}n) rounds and in O(√{ΔlogΔ} + log^* n) rounds when expressing the complexity as a function of Δ and with an optimal dependency on n. In the present paper, we aim to improve our understanding of the deterministic complexity of (Δ+1)-coloring as a function of Δ in a special family of graphs for which significantly faster algorithms are already known. The neighborhood independence θ of a graph is the maximum number of pairwise non-adjacent neighbors of some node of the graph. Notable examples of graphs of bounded neighborhood independence are line graphs of graphs and bounded-rank hypergraphs. It is known that the (2Δ-1)-edge coloring problem and therefore the (Δ+1)-coloring problem in line graphs of graphs can be solved in O(log^{12}Δ+log^* n) rounds. In general, in graphs of neighborhood independence θ = O(1), it is known that (Δ+1)-coloring can be solved in 2^{O(√{logΔ})}+O(log^* n) rounds. In the present paper, we significantly improve the latter result, and we show that in graphs of neighborhood independence θ, a (Δ+1)-coloring can be computed in (θ⋅logΔ)^{O(log logΔ / log log logΔ)}+O(log^* n) rounds and thus in quasipolylogarithmic time in Δ as long as θ is at most polylogarithmic in Δ. Our algorithm can be seen as a generalization of an existing similar, but slightly weaker result for (2Δ-1)-edge coloring. We also show that the approach that leads to this polylogarithmic in Δ algorithm for (2Δ-1)-edge coloring already fails for edge colorings of hypergraphs of rank at least 3. At the core of the fast edge coloring algorithm is an algorithm to divide the edges of a graph into two parts so that up to a multiplicative error of 1+o(1), the maximum degree of the line graph induced by each part is at most half the maximum degree of the original line graph. We show that computing such a bipartition of the edges of the line graph of a hypergraph of rank at least 3 requires time logarithmic in n.
Cite as

Marc Fuchs and Fabian Kuhn. Distributed (Δ+1)-Coloring in Graphs of Bounded Neighborhood Independence. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fuchs_et_al:LIPIcs.OPODIS.2025.23,
  author =	{Fuchs, Marc and Kuhn, Fabian},
  title =	{{Distributed (\Delta+1)-Coloring in Graphs of Bounded Neighborhood Independence}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{23:1--23:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.23},
  URN =		{urn:nbn:de:0030-drops-251968},
  doi =		{10.4230/LIPIcs.OPODIS.2025.23},
  annote =	{Keywords: distributed computing, distributed graph algorithms, graph coloring, list coloring, defective coloring}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.19
Clustering in Varying Metrics

Authors: Deeparnab Chakrabarty, Jonathan Conroy, and Ankita Sarkar

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We introduce the aggregated clustering problem, where one is given T instances of a center-based clustering task over the same n points, but under different metrics. The goal is to open k centers to minimize an aggregate of the clustering costs - e.g., the average or maximum - where the cost is measured via k-center/median/means objectives. More generally, we minimize a norm Ψ over the T cost values. We show that for T ≥ 3, the problem is inapproximable to any finite factor in polynomial time. For T = 2, we give constant-factor approximations. We also show W[2]-hardness when parameterized by k, but obtain f(k,T)poly(n)-time 3-approximations when parameterized by both k and T. When the metrics have structure, we obtain efficient parameterized approximation schemes (EPAS). If all T metrics have bounded ε-scatter dimension, we achieve a (1+ε)-approximation in f(k,T,ε)poly(n) time. If the metrics are induced by edge weights on a common graph G of bounded treewidth tw, and Ψ is the sum function, we get an EPAS in f(T,ε,tw)poly(n,k) time. Conversely, unless (randomized) ETH is false, any finite factor approximation is impossible if parametrized by only T, even when the treewidth is tw = Ω(polylog n).
Cite as

Deeparnab Chakrabarty, Jonathan Conroy, and Ankita Sarkar. Clustering in Varying Metrics. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.FSTTCS.2025.19,
  author =	{Chakrabarty, Deeparnab and Conroy, Jonathan and Sarkar, Ankita},
  title =	{{Clustering in Varying Metrics}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{19:1--19:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.19},
  URN =		{urn:nbn:de:0030-drops-251007},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.19},
  annote =	{Keywords: Clustering, approximation algorithms, LP rounding, parameterized and exact algorithms, dynamic programming, fixed parameter tractability, hardness of approximation}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.40
On the Randomized Locality of Matching Problems in Regular Graphs

Authors: Seri Khoury, Manish Purohit, Aaron Schild, and Joshua R. Wang

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
The main goal in distributed symmetry-breaking is to understand the locality of problems: the radius of the neighborhood that a node must explore to determine its part of a global solution. In this work, we study the locality of matching problems in the family of regular graphs, which is one of the main benchmarks for establishing lower bounds on the locality of symmetry-breaking problems, as well as for obtaining classification results. Our main results are summarized as follows: 1) Approximate matching: We develop randomized algorithms to show that (1 + ε)-approximate matching in regular graphs is truly local, i.e., the locality depends only on ε and is independent of all other graph parameters. Furthermore, as long as the degree Δ is not very small (namely, as long as Δ ≥ poly(1/ε)), this dependence is only logarithmic in 1/ε. This stands in sharp contrast to maximal matching in regular graphs which requires some dependence on the number of nodes n or the degree Δ. 2) Maximal matching: Our techniques further allow us to establish a strong separation between the node-averaged complexity and worst-case complexity of maximal matching in regular graphs, by showing that the former is only O(1). Central to our main technical contribution is a novel martingale-based analysis for the ≈ 40-year-old algorithm by Luby. In particular, our analysis shows that applying one round of Luby’s algorithm on the line graph of a Δ-regular graph results in an almost Δ/2-regular graph.
Cite as

Seri Khoury, Manish Purohit, Aaron Schild, and Joshua R. Wang. On the Randomized Locality of Matching Problems in Regular Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{khoury_et_al:LIPIcs.DISC.2025.40,
  author =	{Khoury, Seri and Purohit, Manish and Schild, Aaron and Wang, Joshua R.},
  title =	{{On the Randomized Locality of Matching Problems in Regular Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{40:1--40:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.40},
  URN =		{urn:nbn:de:0030-drops-248570},
  doi =		{10.4230/LIPIcs.DISC.2025.40},
  annote =	{Keywords: regular graphs, maximum matching, augmenting paths, distributed algorithms, Luby’s algorithm, martingales}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.37
Towards Optimal Distributed Edge Coloring with Fewer Colors

Authors: Manuel Jakob, Yannic Maus, and Florian Schager

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
There is a huge difference in techniques and runtimes of distributed algorithms for problems that can be solved by a sequential greedy algorithm and those that cannot. A prime example of this contrast appears in the edge coloring problem: while (2Δ-1)-edge coloring - where Δ is the maximum degree - can be solved in 𝒪(log^{∗}(n)) rounds on constant-degree graphs, the seemingly minor reduction to (2Δ-2) colors leads to an Ω(log n) lower bound [Chang, He, Li, Pettie & Uitto, SODA'18]. Understanding this sharp divide between very local problems and inherently more global ones remains a central open question in distributed computing and it is a core focus of this paper. As our main contribution we design a deterministic distributed 𝒪(log n)-round reduction from the (2Δ-2)-edge coloring problem to the much easier (2Δ-1)-edge coloring problem. This reduction is optimal, as the (2Δ-2)-edge coloring problem admits an Ω(log n) lower bound that even holds on the class of constant-degree graphs, whereas the 2Δ-1-edge coloring problem can be solved in 𝒪(log^{∗}n) rounds. By plugging in the (2Δ-1)-edge coloring algorithms from [Balliu, Brandt, Kuhn & Olivetti, PODC'22] running in 𝒪(log^{12}Δ + log^{∗} n) rounds, we obtain an optimal runtime of 𝒪(log n) rounds as long as Δ = 2^{𝒪(log^{1/12} n)}. Previously, such an optimal algorithm was only known for the class of constant-degree graphs [Brandt, Maus, Narayanan, Schager & Uitto, SODA'25]. Furthermore, on general graphs our reduction improves the runtime from 𝒪̃(log³ n) to 𝒪̃(log^{5/3} n). In addition, we also obtain an optimal 𝒪(log log n)-round randomized reduction of (2Δ - 2)-edge coloring to (2Δ - 1)-edge coloring. This leads to a 𝒪̃(log^{5/3} log n)-round (2Δ-2)-edge coloring algorithm, which beats the (very recent) previous state-of-the-art taking 𝒪̃(log^{8/3}log n) rounds from [Bourreau, Brandt & Nolin, STOC'25]. Lastly, we obtain an 𝒪(log_Δ n)-round reduction from the (2Δ-1)-edge coloring, albeit to the somewhat harder maximal independent set (MIS) problem.
Cite as

Manuel Jakob, Yannic Maus, and Florian Schager. Towards Optimal Distributed Edge Coloring with Fewer Colors. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 37:1-37:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jakob_et_al:LIPIcs.DISC.2025.37,
  author =	{Jakob, Manuel and Maus, Yannic and Schager, Florian},
  title =	{{Towards Optimal Distributed Edge Coloring with Fewer Colors}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{37:1--37:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.37},
  URN =		{urn:nbn:de:0030-drops-248547},
  doi =		{10.4230/LIPIcs.DISC.2025.37},
  annote =	{Keywords: distributed graph algorithms, edge coloring, LOCAL model}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.25
Model-Agnostic Approximation of Constrained Forest Problems

Authors: Corinna Coupette, Alipasha Montaseri, and Christoph Lenzen

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Constrained Forest Problems (CFPs) as introduced by Goemans and Williamson in 1995 capture a wide range of network design problems with edge subsets as solutions, such as Minimum Spanning Tree, Steiner Forest, and Point-to-Point Connection. While individual CFPs have been studied extensively in individual computational models, a unified approach to solving general CFPs in multiple computational models has been lacking. Against this background, we present the shell-decomposition algorithm, a model-agnostic meta-algorithm that efficiently computes a (2+ε)-approximation to CFPs for a broad class of forest functions. The shell-decomposition algorithm isolates the problem-specific hardness of individual CFPs in a single computational subroutine, breaking the remainder of the computation into fundamental tasks that are studied extensively in a wide range of computational models. In contrast to prior work, our framework is compatible with the use of approximate distances. To demonstrate the power and flexibility of this result, we instantiate our algorithm for three fundamental, NP-hard CFPs (Steiner Forest, Point-to-Point Connection, and Facility Placement and Connection) in three different computational models (Congest, PRAM, and Multi-Pass Streaming). For constant ε, we obtain the following (2+ε)-approximations in the Congest model: [(1)] 1) For Steiner Forest specified via input components (SF-IC), where each node knows the identifier of one of k disjoint subsets of V (the input components), we achieve a deterministic (2+ε)-approximation in 𝒪̃(√n+D+k) rounds, where D is the hop diameter of the graph, significantly improving over the state of the art. 2) For Steiner Forest specified via symmetric connection requests (SF-SCR), where connection requests are issued to pairs of nodes u,v ∈ V, we leverage randomized equality testing to reduce the running time to 𝒪̃(√n+D), succeeding with high probability. 3) For Point-to-Point Connection, we provide a (2+ε)-approximation in 𝒪̃(√n+D) rounds. 4) For Facility Placement and Connection, a relative of non-metric Uncapacitated Facility Location, we obtain a (2+ε)-approximation in 𝒪̃(√n + D) rounds. We further show how to replace the √n+D term by the complexity of solving Partwise Aggregation, achieving (near-)universal optimality in any setting in which a solution to Partwise Aggregation in near-shortcut-quality time is known. Notably, all of our concrete results can be derived with relative ease once our model-agnostic meta-algorithm has been specified. This demonstrates the power of our modularization approach to algorithm design.
Cite as

Corinna Coupette, Alipasha Montaseri, and Christoph Lenzen. Model-Agnostic Approximation of Constrained Forest Problems. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 25:1-25:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{coupette_et_al:LIPIcs.DISC.2025.25,
  author =	{Coupette, Corinna and Montaseri, Alipasha and Lenzen, Christoph},
  title =	{{Model-Agnostic Approximation of Constrained Forest Problems}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{25:1--25:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.25},
  URN =		{urn:nbn:de:0030-drops-248420},
  doi =		{10.4230/LIPIcs.DISC.2025.25},
  annote =	{Keywords: Distributed Graph Algorithms, Model-Agnostic Algorithms, Steiner Forest}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.11
New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs

Authors: Alkida Balliu, Corinna Coupette, Antonio Cruciani, Francesco d'Amore, Massimo Equi, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, and Jukka Suomela

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
In this work, we give two results that put new limits on distributed quantum advantage in the context of the LOCAL model of distributed computing: 1) We show that there is no distributed quantum advantage for any linear program. Put otherwise, if there is a quantum-LOCAL algorithm 𝒜 that finds an α-approximation of some linear optimization problem Π in T communication rounds, we can construct a classical, deterministic LOCAL algorithm 𝒜' that finds an α-approximation of Π in T rounds. As a corollary, all classical lower bounds for linear programs, including the KMW bound, hold verbatim in quantum-LOCAL. 2) Using the above result, we show that there exists a locally checkable labeling problem (LCL) for which quantum-LOCAL is strictly weaker than the classical deterministic SLOCAL model. Our results extend from quantum-LOCAL to finitely dependent and non-signaling distributions, and one of the corollaries of our work is that the non-signaling model and the SLOCAL model are incomparable in the context of LCL problems: By prior work, there exists an LCL problem for which SLOCAL is strictly weaker than the non-signaling model, and our work provides a separation in the opposite direction.
Cite as

Alkida Balliu, Corinna Coupette, Antonio Cruciani, Francesco d'Amore, Massimo Equi, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, and Jukka Suomela. New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2025.11,
  author =	{Balliu, Alkida and Coupette, Corinna and Cruciani, Antonio and d'Amore, Francesco and Equi, Massimo and Lievonen, Henrik and Modanese, Augusto and Olivetti, Dennis and Suomela, Jukka},
  title =	{{New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.11},
  URN =		{urn:nbn:de:0030-drops-248280},
  doi =		{10.4230/LIPIcs.DISC.2025.11},
  annote =	{Keywords: linear programming, distributed quantum advantage, quantum-LOCAL model, SLOCAL model, online-LOCAL model, non-signaling distributions, locally checkable labeling problems, dequantization}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.12
Distributed Computation with Local Advice

Authors: Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, and Jukka Suomela

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Algorithms with advice have received ample attention in the distributed and online settings, and they have recently proven useful also in dynamic settings. In this work we study local computation with advice: the goal is to solve a graph problem Π with a distributed algorithm in T(Δ) communication rounds, for some function T that only depends on the maximum degree Δ of the graph, and the key question is how many bits of advice per node are needed. Some of our results regard Locally Checkable Labeling problems (LCLs), which is an important family of problems that includes various coloring and orientation problems on finite-degree graphs. These are constraint-satisfaction graph problems that can be defined with a finite set of valid input/output-labeled neighborhoods. Our main results are: 1) Any locally checkable labeling problem can be solved with only 1 bit of advice per node in graphs with sub-exponential growth (the number of nodes within radius r is sub-exponential in r; for example, grids are such graphs). Moreover, we can make the set of nodes that carry advice bits arbitrarily sparse. As a corollary, any locally checkable labeling problem admits a locally checkable proof with 1 bit per node in graphs with sub-exponential growth. 2) The assumption of sub-exponential growth is complemented by a conditional lower bound: assuming the Exponential-Time Hypothesis, there are locally checkable labeling problems that cannot be solved in general with any constant number of bits per node. 3) In any graph we can find an almost-balanced orientation (indegrees and outdegrees differ by at most one) with 1 bit of advice per node, and again we can make the advice arbitrarily sparse. As a corollary, we can also compress an arbitrary subset of edges so that a node of degree d stores only d/2 + 2 bits, and we can decompress it locally, in T(Δ) rounds. 4) In any graph of maximum degree Δ, we can find a Δ-coloring (if it exists) with 1 bit of advice per node, and again, we can make the advice arbitrarily sparse. 5) In any 3-colorable graph, we can find a 3-coloring with 1 bit of advice per node. As a corollary, in bounded-degree graphs there is a locally checkable proof that certifies 3-colorability with 1 bit of advice per node, while prior work shows that this is not possible with a proof labeling scheme (PLS), which is a more restricted setting where the verifier can only see up to distance 1. Our work shows that for many problems the key threshold is not whether we can achieve 1 bit of advice per node, but whether we can make the advice arbitrarily sparse. To formalize this idea, we develop a general framework of composable schemas that enables us to build algorithms for local computation with advice in a modular fashion: once we have (1) a schema for solving Π₁ and (2) a schema for solving Π₂ assuming an oracle for Π₁, we can also compose them and obtain (3) a schema that solves Π₂ without the oracle. It turns out that many natural problems admit composable schemas, all of them can be solved with only 1 bit of advice, and we can make the advice arbitrarily sparse.
Cite as

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, and Jukka Suomela. Distributed Computation with Local Advice. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2025.12,
  author =	{Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Nowicki, Krzysztof and Olivetti, Dennis and Rotenberg, Eva and Suomela, Jukka},
  title =	{{Distributed Computation with Local Advice}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.12},
  URN =		{urn:nbn:de:0030-drops-248295},
  doi =		{10.4230/LIPIcs.DISC.2025.12},
  annote =	{Keywords: Distributed graph algorithms, LOCAL model, computation with advice, locally checkable labeling problems, proof labeling schemes, locally checkable proofs, graph coloring, exponential-time hypothesis}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.13
Towards Fully Automatic Distributed Lower Bounds

Authors: Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, and Joonatan Saarhelo

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
In the past few years, a successful line of research has led to lower bounds for several fundamental local graph problems in the distributed setting. These results were obtained via a technique called round elimination. On a high level, the round elimination technique can be seen as a recursive application of a function that takes as input a problem Π and outputs a problem Π' that is one round easier than Π. Applying this function recursively to concrete problems of interest can be highly nontrivial, which is one of the reasons that has made the technique difficult to approach. The contribution of our paper is threefold. Firstly, we develop a new and fully automatic method for finding so-called fixed point relaxations under round elimination. The detection of a non-0-round solvable fixed point relaxation of a problem Π immediately implies lower bounds of Ω(log_Δ n) and Ω(log_Δ log n) rounds for deterministic and randomized algorithms for Π, respectively. Secondly, we show that this automatic method is indeed useful, by obtaining lower bounds for defective coloring problems. More precisely, as an application of our procedure, we show that the problem of coloring the nodes of a graph with 3 colors and defect at most (Δ - 3)/2 requires Ω(log_Δ n) rounds for deterministic algorithms and Ω(log_Δ log n) rounds for randomized ones. Additionally, we provide a simplified proof for an existing defective coloring lower bound. We note that lower bounds for coloring problems are notoriously challenging to obtain, both in general, and via the round elimination technique. {Both the first and (indirectly) the second contribution build on our third contribution: a new method to compute the one-round easier problem Π' in the round elimination framework. This method heavily simplifies the usage of the round elimination technique, and in fact it has been successfully exploited in a recent work in order to prove quantum advantage in the distributed setting [STOC '25].}
Cite as

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, and Joonatan Saarhelo. Towards Fully Automatic Distributed Lower Bounds. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2025.13,
  author =	{Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Olivetti, Dennis and Saarhelo, Joonatan},
  title =	{{Towards Fully Automatic Distributed Lower Bounds}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.13},
  URN =		{urn:nbn:de:0030-drops-248308},
  doi =		{10.4230/LIPIcs.DISC.2025.13},
  annote =	{Keywords: round elimination, lower bounds, defective coloring}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.102
A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull

Authors: Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
For a planar point set P, its convex hull is the smallest convex polygon that encloses all points in P. The construction of the convex hull from an array I_P containing P is a fundamental problem in computational geometry. By sorting I_P in lexicographical order, one can construct the convex hull of P in O(n log n) time which is worst-case optimal. Standard worst-case analysis, however, has been criticized as overly coarse or pessimistic, and researchers search for more refined analyses. For an algorithm A, worst-case analysis fixes n, and considers the maximum running time of A across all size-n point sets P and permutations I_P of P. Output-sensitive analysis fixes n and k, and considers the maximum running time across all size-n points sets P with k hull points and permutations I_P of P. Universal analysis provides an even stronger guarantee. It fixes a point set P and considers the maximum running time across all permutations I_P of P. Kirkpatrick, McQueen, and Seidel [SICOMP'86] consider output-sensitive analysis. If the convex hull of P contains k points, then their algorithm runs in O(n log k) time. Afshani, Barbay, Chan [FOCS'07] prove that the algorithm by Kirkpatrick, McQueen, and Seidel is also universally optimal. Their proof restricts the model of computation to any algebraic decision tree model where the test functions have at most constant degree and at most a constant number of arguments. They rely upon involved algebraic arguments to construct a lower bound for each point set P that matches the universal running time of [SICOMP'86]. We provide a different proof of universal optimality. Instead of restricting the computational model, we further specify the output. We require as output (1) the convex hull, and (2) for each internal point of P a witness for it being internal. Our argument is shorter, perhaps simpler, and applicable in more general models of computation.
Cite as

Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann. A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 102:1-102:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.ESA.2025.102,
  author =	{van der Hoog, Ivor and Rotenberg, Eva and Rutschmann, Daniel},
  title =	{{A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{102:1--102:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.102},
  URN =		{urn:nbn:de:0030-drops-245715},
  doi =		{10.4230/LIPIcs.ESA.2025.102},
  annote =	{Keywords: Convex hull, Combinatorial proofs, Universal optimality}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.5
External-Memory Priority Queues with Optimal Insertions

Authors: Gerth Stølting Brodal, Michael T. Goodrich, John Iacono, Jared Lo, Ulrich Meyer, Victor Pagan, Nodari Sitchinava, and Rolf Svenning

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We present an external-memory priority queue structure supporting Insert and DeleteMin with amortized 𝒪(1) and 𝒪(lg N) comparisons, respectively, and amortized 𝒪(1/B) and 𝒪(1/B log_{M/B} N/B) I/Os, respectively. Here, M is the size of the internal memory, B is the block size of I/Os between internal and external memory, and N is the number of elements in the priority queue just before an operation is performed. Previous external-memory priority queues required amortized 𝒪(lg N) comparisons and 𝒪(1/B log_{M/B} N/B) I/Os for both Insert and DeleteMin. The construction requires the minimal assumption M ≥ 2B.
Cite as

Gerth Stølting Brodal, Michael T. Goodrich, John Iacono, Jared Lo, Ulrich Meyer, Victor Pagan, Nodari Sitchinava, and Rolf Svenning. External-Memory Priority Queues with Optimal Insertions. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brodal_et_al:LIPIcs.ESA.2025.5,
  author =	{Brodal, Gerth St{\o}lting and Goodrich, Michael T. and Iacono, John and Lo, Jared and Meyer, Ulrich and Pagan, Victor and Sitchinava, Nodari and Svenning, Rolf},
  title =	{{External-Memory Priority Queues with Optimal Insertions}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.5},
  URN =		{urn:nbn:de:0030-drops-244734},
  doi =		{10.4230/LIPIcs.ESA.2025.5},
  annote =	{Keywords: priority queues, external memory, cache aware, amortized complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.25
Instance-Optimal Imprecise Convex Hull

Authors: Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, and Sampson Wong

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Imprecise measurements of a point set P = (p₁, …, p_n) can be modelled by a family of regions F = (R₁, …, R_n), where each imprecise region R_i ∈ F contains a unique point p_i ∈ P. A retrieval models an accurate measurement by replacing an imprecise region R_i with its corresponding point p_i. We construct the convex hull of an imprecise point set in the plane, by determining the cyclic ordering of the convex hull vertices of P as efficiently as possible. Efficiency is interpreted in two ways: (i) minimising the number of retrievals, and (ii) the computation time to determine the set of regions that must be retrieved. Previous works focused on only one of these two aspects: either minimising retrievals or optimising algorithmic runtime. Our contribution is the first to simultaneously achieve both. Let r(F, P) denote the minimal number of retrievals required by any algorithm to determine the convex hull of P for a given instance (F, P). For a family F of n constant-complexity polygons, our main result is a reconstruction algorithm that performs Θ(r(F, P)) retrievals in O(r(F, P) log³ n) time. Compared to previous approaches that achieve optimal retrieval counts, we improve the runtime per retrieval from polynomial to polylogarithmic. We extend the generality of previous results to simple k-gons, to pairwise disjoint disks with radii in [1,k], and to unit disks where at most k disks overlap in a single point. Our runtime scales linearly with k.
Cite as

Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, and Sampson Wong. Instance-Optimal Imprecise Convex Hull. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ESA.2025.25,
  author =	{de Berg, Sarita and van der Hoog, Ivor and Rotenberg, Eva and Rutschmann, Daniel and Wong, Sampson},
  title =	{{Instance-Optimal Imprecise Convex Hull}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{25:1--25:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.25},
  URN =		{urn:nbn:de:0030-drops-244932},
  doi =		{10.4230/LIPIcs.ESA.2025.25},
  annote =	{Keywords: convex hull, imprecise geometry preprocessing model, partial information}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.70
Improved Parallel Derandomization via Finite Automata with Applications

Authors: Jeff Giliberti and David G. Harris

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A central approach to algorithmic derandomization is the construction of small-support probability distributions that "fool” randomized algorithms, often enabling efficient parallel (NC) implementations. An abstraction of this idea is fooling polynomial-space statistical tests computed via finite automata [Sivakumar STOC'02]; this encompasses a wide range of properties including k-wise independence and sums of random variables. We present new parallel algorithms to fool finite-state automata, with significantly reduced processor complexity. Briefly, our approach is to iteratively sparsify distributions using a work-efficient lattice rounding routine and maintain accuracy by tracking an aggregate weighted error that is determined by the Lipschitz value of the statistical tests being fooled. We illustrate with improved applications to the Gale-Berlekamp Switching Game and to approximate MAX-CUT via SDP rounding. These involve further several optimizations, such as the truncation of the state space of the automata and FFT-based convolutions to compute transition probabilities efficiently.
Cite as

Jeff Giliberti and David G. Harris. Improved Parallel Derandomization via Finite Automata with Applications. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 70:1-70:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{giliberti_et_al:LIPIcs.ESA.2025.70,
  author =	{Giliberti, Jeff and Harris, David G.},
  title =	{{Improved Parallel Derandomization via Finite Automata with Applications}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{70:1--70:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.70},
  URN =		{urn:nbn:de:0030-drops-245381},
  doi =		{10.4230/LIPIcs.ESA.2025.70},
  annote =	{Keywords: Parallel Algorithms, Derandomization, MAX-CUT, Gale-Berlekamp Switching Game}
}
  • Refine by Type
  • 33 Document/PDF
  • 29 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 25 2025
  • 1 2023
  • 3 2022

  • Refine by Author
  • 5 Kuhn, Fabian
  • 4 Balliu, Alkida
  • 4 Brandt, Sebastian
  • 4 Modanese, Augusto
  • 4 Olivetti, Dennis
  • Show More...

  • Refine by Series/Journal
  • 33 LIPIcs

  • Refine by Classification
  • 15 Theory of computation → Distributed algorithms
  • 5 Mathematics of computing → Graph algorithms
  • 4 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Computational geometry
  • Show More...

  • Refine by Keyword
  • 4 locally checkable labeling problems
  • 3 Distributed Graph Algorithms
  • 2 Distributed algorithms
  • 2 LOCAL model
  • 2 defective coloring
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact