17 Search Results for "Mallmann-Trenn, Frederik"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.9
Small Space Encoding and Recognition of k-Palindromic Prefixes

Authors: Gabriel Bathie, Jonas Ellert, and Tatiana Starikovskaya

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Palindromes are non-empty strings that read the same forward and backward. We study the problem of recognizing so-called k-palindromic strings, which can be represented as the concatenation of exactly k palindromes. [Rubinchik and Shur, MFCS 2020] showed that the problem is solvable in linear space and time. We present a read-only algorithm that recognizes all k-palindromic prefixes of a string T of length n in O(n ⋅ 6^{k²} ⋅ log^k n) time and O(6^{k²} ⋅ log^k n) space. As a corollary, we also obtain a read-only algorithm for computing the palindromic length of T, i.e., the smallest k such that T is k-palindromic, in O(n ⋅ 6^{k²} ⋅ log^⌈k/2⌉ n) time and O(6^{k²} ⋅ log^⌈k/2⌉ n) space.
Cite as

Gabriel Bathie, Jonas Ellert, and Tatiana Starikovskaya. Small Space Encoding and Recognition of k-Palindromic Prefixes. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bathie_et_al:LIPIcs.ISAAC.2025.9,
  author =	{Bathie, Gabriel and Ellert, Jonas and Starikovskaya, Tatiana},
  title =	{{Small Space Encoding and Recognition of k-Palindromic Prefixes}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.9},
  URN =		{urn:nbn:de:0030-drops-249178},
  doi =		{10.4230/LIPIcs.ISAAC.2025.9},
  annote =	{Keywords: palindromic length, read-only algorithms, palindromes}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.36
Streaming Periodicity with Mismatches, Wildcards, and Edits

Authors: Taha El Ghazi and Tatiana Starikovskaya

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In this work, we study the problem of detecting periodic trends in strings. While detecting exact periodicity has been studied extensively, real-world data is often noisy, where small deviations or mismatches occur between repetitions. This work focuses on a generalized approach to period detection that efficiently handles noise. Given a string S of length n, the task is to identify integers p such that the prefix and the suffix of S, each of length n-p+1, are similar under a given distance measure. Ergün et al. [APPROX-RANDOM 2017] were the first to study this problem in the streaming model under the Hamming distance. In this work, we combine, in a non-trivial way, the Hamming distance sketch of Clifford et al. [SODA 2019] and the structural description of the k-mismatch occurrences of a pattern in a text by Charalampopoulos et al. [FOCS 2020] to present a more efficient streaming algorithm for period detection under the Hamming distance. As a corollary, we derive a streaming algorithm for detecting periods of strings which may contain wildcards, a special symbol that match any character of the alphabet. Our algorithm is not only more efficient than that of Ergün et al. [TCS 2020], but it also operates without their assumption that the string must be free of wildcards in its final characters. Additionally, we introduce the first two-pass streaming algorithm for computing periods under the edit distance by leveraging and extending the Bhattacharya-Koucký’s grammar decomposition technique [STOC 2023].
Cite as

Taha El Ghazi and Tatiana Starikovskaya. Streaming Periodicity with Mismatches, Wildcards, and Edits. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{elghazi_et_al:LIPIcs.ISAAC.2025.36,
  author =	{El Ghazi, Taha and Starikovskaya, Tatiana},
  title =	{{Streaming Periodicity with Mismatches, Wildcards, and Edits}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.36},
  URN =		{urn:nbn:de:0030-drops-249446},
  doi =		{10.4230/LIPIcs.ISAAC.2025.36},
  annote =	{Keywords: approximate periods, pattern matching, streaming algorithms}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.27
On the h-Majority Dynamics with Many Opinions

Authors: Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis, and Emanuele Natale

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

Abstract
We present the first upper bound on the convergence time to consensus of the well-known h-majority dynamics with k opinions, in the synchronous setting, for h and k that are both non-constant values. We suppose that, at the beginning of the process, there is some initial additive bias towards some plurality opinion, that is, there is an opinion that is supported by x nodes while any other opinion is supported by strictly fewer nodes. We prove that, with high probability, if the bias is ω(√x) and the initial plurality opinion is supported by at least x = ω(log n) nodes, then the process converges to plurality consensus in O(log n) rounds whenever h = ω(n log n / x). A main corollary is the following: if k = o(n / log n) and the process starts from an almost-balanced configuration with an initial bias of magnitude ω(√{n/k}) towards the initial plurality opinion, then any function h = ω(k log n) suffices to guarantee convergence to consensus in O(log n) rounds, with high probability. Our upper bound shows that the lower bound of Ω(k / h²) rounds to reach consensus given by Becchetti et al. (2017) cannot be pushed further than Ω̃(k / h). Moreover, the bias we require is asymptotically smaller than the Ω(√{nlog n}) bias that guarantees plurality consensus in the 3-majority dynamics: in our case, the required bias is at most any (arbitrarily small) function in ω(√x) for any value of k ≥ 2.
Cite as

Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis, and Emanuele Natale. On the h-Majority Dynamics with Many Opinions. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 27:1-27:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{damore_et_al:LIPIcs.DISC.2025.27,
  author =	{d'Amore, Francesco and D'Archivio, Niccol\`{o} and Giakkoupis, George and Natale, Emanuele},
  title =	{{On the h-Majority Dynamics with Many Opinions}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{27:1--27: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.27},
  URN =		{urn:nbn:de:0030-drops-248448},
  doi =		{10.4230/LIPIcs.DISC.2025.27},
  annote =	{Keywords: Distributed Algorithms, Randomized Algorithms, Markov Chains, Consensus Problem, Opinion dynamics, Plurality Consensus}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.40
Sublinear Space Graph Algorithms in the Continual Release Model

Authors: Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, and Felix Zhou

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
The graph continual release model of differential privacy seeks to produce differentially private solutions to graph problems under a stream of edge updates where new private solutions are released after each update. Thus far, previously known edge-differentially private algorithms for most graph problems including densest subgraph and matchings in the continual release setting only output real-value estimates (not vertex subset solutions) and do not use sublinear space. Instead, they rely on computing exact graph statistics on the input [Hendrik Fichtenberger et al., 2021; Shuang Song et al., 2018]. In this paper, we leverage sparsification to address the above shortcomings for edge-insertion streams. Our edge-differentially private algorithms use sublinear space with respect to the number of edges in the graph while some also achieve sublinear space in the number of vertices in the graph. In addition, for the densest subgraph problem, we also output edge-differentially private vertex subset solutions; no previous graph algorithms in the continual release model output such subsets. We make novel use of assorted sparsification techniques from the non-private streaming and static graph algorithms literature to achieve new results in the sublinear space, continual release setting. This includes algorithms for densest subgraph, maximum matching, as well as the first continual release k-core decomposition algorithm. We also develop a novel sparse level data structure for k-core decomposition that may be of independent interest. To complement our insertion-only algorithms, we conclude with polynomial additive error lower bounds for edge-privacy in the fully dynamic setting, where only logarithmic lower bounds were previously known.
Cite as

Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, and Felix Zhou. Sublinear Space Graph Algorithms in the Continual Release Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 40:1-40:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{epasto_et_al:LIPIcs.APPROX/RANDOM.2025.40,
  author =	{Epasto, Alessandro and Liu, Quanquan C. and Mukherjee, Tamalika and Zhou, Felix},
  title =	{{Sublinear Space Graph Algorithms in the Continual Release Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{40:1--40:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.40},
  URN =		{urn:nbn:de:0030-drops-244064},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.40},
  annote =	{Keywords: Differential Privacy, Continual Release, Densest Subgraph, k-Core Decomposition, Maximum Matching}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.24
Computational Geometry with Probabilistically Noisy Primitive Operations

Authors: David Eppstein, Michael T. Goodrich, and Vinesh Sridhar

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Much prior work has been done on designing computational geometry algorithms that handle input degeneracies, data imprecision, and arithmetic round-off errors. We take a new approach, inspired by the noisy sorting literature, and study computational geometry algorithms subject to noisy Boolean primitive operations in which, e.g., the comparison "is point q above line 𝓁?" returns the wrong answer with some fixed probability. We propose a novel technique called path-guided pushdown random walks that generalizes the results of noisy sorting. We apply this technique to solve point-location, plane-sweep, convex hulls in 2D and 3D, and Delaunay triangulations for noisy primitives in optimal time with high probability.
Cite as

David Eppstein, Michael T. Goodrich, and Vinesh Sridhar. Computational Geometry with Probabilistically Noisy Primitive Operations. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.WADS.2025.24,
  author =	{Eppstein, David and Goodrich, Michael T. and Sridhar, Vinesh},
  title =	{{Computational Geometry with Probabilistically Noisy Primitive Operations}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.24},
  URN =		{urn:nbn:de:0030-drops-242552},
  doi =		{10.4230/LIPIcs.WADS.2025.24},
  annote =	{Keywords: Computational geometry, noisy comparisons, random walks}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.103
Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds

Authors: Michael Kapralov, Akash Kumar, Silvio Lattanzi, Aida Mousavifar, and Weronika Wrzos-Kaminska

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Testing graph cluster structure has been a central object of study in property testing since the foundational work of Goldreich and Ron [STOC'96] on expansion testing, i.e. the problem of distinguishing between a single cluster (an expander) and a graph that is far from a single cluster. More generally, a (k, ε)-clusterable graph G is a graph whose vertex set admits a partition into k induced expanders, each with outer conductance bounded by ε. A recent line of work initiated by Czumaj, Peng and Sohler [STOC'15] has shown how to test whether a graph is close to (k, ε)-clusterable, and to locally determine which cluster a given vertex belongs to with misclassification rate ≈ ε, but no sublinear time algorithms for learning the structure of inter-cluster connections are known. As a simple example, can one locally distinguish between the "cluster graph" forming a line and a clique? In this paper, we consider the problem of testing the hierarchical cluster structure of (k, ε)-clusterable graphs in sublinear time. Our measure of hierarchical clusterability is the well-established Dasgupta cost, and our main result is an algorithm that approximates Dasgupta cost of a (k, ε)-clusterable graph in sublinear time, using a small number of randomly chosen seed vertices for which cluster labels are known. Our main result is an O(√{log k}) approximation to Dasgupta cost of G in ≈ n^{1/2+O(ε)} time using ≈ n^{1/3} seeds, effectively giving a sublinear time simulation of the algorithm of Charikar and Chatziafratis [SODA'17] on clusterable graphs. To the best of our knowledge, ours is the first result on approximating the hierarchical clustering properties of such graphs in sublinear time.
Cite as

Michael Kapralov, Akash Kumar, Silvio Lattanzi, Aida Mousavifar, and Weronika Wrzos-Kaminska. Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 103:1-103:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kapralov_et_al:LIPIcs.ICALP.2025.103,
  author =	{Kapralov, Michael and Kumar, Akash and Lattanzi, Silvio and Mousavifar, Aida and Wrzos-Kaminska, Weronika},
  title =	{{Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{103:1--103:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.103},
  URN =		{urn:nbn:de:0030-drops-234804},
  doi =		{10.4230/LIPIcs.ICALP.2025.103},
  annote =	{Keywords: Sublinear algorithms, Hierarchical Clustering, Dasgupta’s Cost}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.117
Incremental Approximate Single-Source Shortest Paths with Predictions

Authors: Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Helia Niaparast, and Shikha Singh

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The algorithms-with-predictions framework has been used extensively to develop online algorithms with improved beyond-worst-case competitive ratios. Recently, there is growing interest in leveraging predictions for designing data structures with improved beyond-worst-case running times. In this paper, we study the fundamental data structure problem of maintaining approximate shortest paths in incremental graphs in the algorithms-with-predictions model. Given a sequence σ of edges that are inserted one at a time, the goal is to maintain approximate shortest paths from the source to each vertex in the graph at each time step. Before any edges arrive, the data structure is given a prediction of the online edge sequence σ̂ which is used to "warm start" its state. As our main result, we design a learned algorithm that maintains (1+ε)-approximate single-source shortest paths, which runs in Õ(m η log W/ε) time, where W is the weight of the heaviest edge and η is the prediction error. We show these techniques immediately extend to the all-pairs shortest-path setting as well. Our algorithms are consistent (performing nearly as fast as the offline algorithm) when predictions are nearly perfect, have a smooth degradation in performance with respect to the prediction error and, in the worst case, match the best offline algorithm up to logarithmic factors. That is, the algorithms are "ideal" in the algorithms-with-predictions model. As a building block, we study the offline incremental approximate single-source shortest-path (SSSP) problem. In the offline incremental SSSP problem, the edge sequence σ is known a priori and the goal is to construct a data structure that can efficiently return the length of the shortest paths in the intermediate graph G_t consisting of the first t edges, for all t. Note that the offline incremental problem is defined in the worst-case setting (without predictions) and is of independent interest.
Cite as

Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Helia Niaparast, and Shikha Singh. Incremental Approximate Single-Source Shortest Paths with Predictions. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 117:1-117:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mccauley_et_al:LIPIcs.ICALP.2025.117,
  author =	{McCauley, Samuel and Moseley, Benjamin and Niaparast, Aidin and Niaparast, Helia and Singh, Shikha},
  title =	{{Incremental Approximate Single-Source Shortest Paths with Predictions}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{117:1--117:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.117},
  URN =		{urn:nbn:de:0030-drops-234946},
  doi =		{10.4230/LIPIcs.ICALP.2025.117},
  annote =	{Keywords: Algorithms with Predictions, Shortest Paths, Approximation Algorithms, Dynamic Graph Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.87
IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates

Authors: Giordano Giambartolomei, Frederik Mallmann-Trenn, and Raimundo Saona

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given distribution. Upon observing each value, the gambler either accepts it as a reward, or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is to maximise the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. This model has been studied with infinite, finite and unknown number of values. When the gambler faces a random number of values, the model is said to have a random horizon. We consider the model in which the gambler is given a priori knowledge of the horizon’s distribution. Alijani et al. (2020) designed a single-threshold algorithm achieving a ratio of 1/2 when the random horizon has an increasing hazard rate and is independent of the values. We prove that with a single threshold, a ratio of 1/2 is actually achievable for several larger classes of horizon distributions, with the largest being known as the 𝒢 class in reliability theory. Moreover, we show that this does not extend to its dual, the ̅𝒢 class (which includes the decreasing hazard rate class), while it can be extended to low-variance horizons. Finally, we construct the first example of a family of horizons, for which multiple thresholds are necessary to achieve a nonzero ratio. We establish that the Secretary Problem optimal stopping rule provides one such algorithm, paving the way towards the study of the model beyond single-threshold algorithms.
Cite as

Giordano Giambartolomei, Frederik Mallmann-Trenn, and Raimundo Saona. IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 87:1-87:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{giambartolomei_et_al:LIPIcs.ICALP.2025.87,
  author =	{Giambartolomei, Giordano and Mallmann-Trenn, Frederik and Saona, Raimundo},
  title =	{{IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{87:1--87:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.87},
  URN =		{urn:nbn:de:0030-drops-234643},
  doi =		{10.4230/LIPIcs.ICALP.2025.87},
  annote =	{Keywords: Online algorithms, Prophet Inequality, Random Horizon, Secretary Problem}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.36
Distributed Branching Random Walks and Their Applications

Authors: Vijeth Aradhya, Seth Gilbert, and Thorsten Götte

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
In recent years, the explosion of big data and analytics has necessitated distributed storage and processing with several compute nodes (e.g., multiple datacenters). These nodes collaboratively perform parallel computation, where the data is typically partitioned across these nodes to ensure scalability, redundancy and load-balancing. But the nodes may not always be co-located; in many cases, they are part of a larger communication network. Since those nodes only need to communicate among themselves, a key challenge is to design efficient routes catered to that subnetwork. In this work, we initiate the study of distributed sampling and routing problems for subnetworks in any well-connected network. Given any network G = (V, E) with mixing time τ_mix, consider the canonical problem of permutation routing [Ghaffari, Kuhn and Su, PODC 2017] that aims to minimize both congestion and dilation of the routes, where the demands (i.e., set of source-terminal pairs) are such that each node sends or receives number of messages proportional to its degree. We show that the permutation routing problem, when demands are restricted to any subset S ⊆ V (i.e., subnetwork), can be solved in exp(O(√(log|S|))) ⋅ Õ(τ_mix) rounds (where Õ(⋅) hides polylogarithmic factors of |V|). This means that the running time depends subpolynomially on the subnetwork size (i.e., not on the entire network size). The ability to solve permutation routing efficiently immediately implies that a large class of parallel algorithms can be simulated efficiently on the subnetwork. As a prerequisite to constructing efficient routes, we design and analyze distributed branching random walks that distribute tokens started by the nodes in the subnetwork. At a high-level, these algorithms operate by always moving each token according to a (lazy) simple random walk, but also branching a token into multiple tokens at some specified intervals; ultimately, if a node starts a branching walk, with its id in a token, then by the end of execution, several tokens with its id would be randomly distributed among the nodes. As these random walks can be started by many nodes, a crucial challenge is to ensure low-congestion, which is a primary focus of this paper.
Cite as

Vijeth Aradhya, Seth Gilbert, and Thorsten Götte. Distributed Branching Random Walks and Their Applications. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aradhya_et_al:LIPIcs.OPODIS.2024.36,
  author =	{Aradhya, Vijeth and Gilbert, Seth and G\"{o}tte, Thorsten},
  title =	{{Distributed Branching Random Walks and Their Applications}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.36},
  URN =		{urn:nbn:de:0030-drops-225723},
  doi =		{10.4230/LIPIcs.OPODIS.2024.36},
  annote =	{Keywords: Distributed Graph Algorithms, Random Walks, Permutation Routing}
}
Document
DOI: 10.4230/LIPIcs.DISC.2024.27
Sorting in One and Two Rounds Using t-Comparators

Authors: Ran Gelles, Zvi Lotker, and Frederik Mallmann-Trenn

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
We examine sorting algorithms for n elements whose basic operation is comparing t elements simultaneously (a t-comparator). We focus on algorithms that use only a single round or two rounds - comparisons performed in the second round depend on the outcomes of the first round comparators. Algorithms with a small number of rounds are well-suited to distributed settings in which communication rounds are costly. We design deterministic and randomized algorithms. In the deterministic case, we show an interesting relation to design theory (namely, to 2-Steiner systems), which yields a single-round optimal algorithm for n = t^{2^k} with any k ≥ 1 and a variety of possible values of t. For some values of t, however, no algorithm can reach the optimal (information-theoretic) bound on the number of comparators. For this case (and any other n and t), we show an algorithm that uses at most three times as many comparators as the theoretical bound. We also design a randomized Las-Vegas two-round sorting algorithm for any n and t. Our algorithm uses an asymptotically optimal number of O(max(n^{3/2}/t²,n/t)) comparators, with high probability, i.e., with probability at least 1-1/n. The analysis of this algorithm involves the gradual unveiling of randomness, using a novel technique which we coin the binary tree of deferred randomness.
Cite as

Ran Gelles, Zvi Lotker, and Frederik Mallmann-Trenn. Sorting in One and Two Rounds Using t-Comparators. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gelles_et_al:LIPIcs.DISC.2024.27,
  author =	{Gelles, Ran and Lotker, Zvi and Mallmann-Trenn, Frederik},
  title =	{{Sorting in One and Two Rounds Using t-Comparators}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.27},
  URN =		{urn:nbn:de:0030-drops-212539},
  doi =		{10.4230/LIPIcs.DISC.2024.27},
  annote =	{Keywords: Sorting, Steiner-System, Round Complexity, Deferred Randomness}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.148
Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol

Authors: Frederik Mallmann-Trenn, Yannic Maus, and Dominik Pajak

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We study a process of averaging in a distributed system with noisy communication. Each of the agents in the system starts with some value and the goal of each agent is to compute the average of all the initial values. In each round, one pair of agents is drawn uniformly at random from the whole population, communicates with each other and each of these two agents updates their local value based on their own value and the received message. The communication is noisy and whenever an agent sends any value v, the receiving agent receives v+N, where N is a zero-mean Gaussian random variable. The two quality measures of interest are (i) the total sum of squares TSS(t), which measures the sum of square distances from the average load to the initial average and (ii) bar{phi}(t), which measures the sum of square distances from the average load to the running average (average at time t). It is known that the simple averaging protocol - in which an agent sends its current value and sets its new value to the average of the received value and its current value - converges eventually to a state where bar{phi}(t) is small. It has been observed that TSS(t), due to the noise, eventually diverges and previous research - mostly in control theory - has focused on showing eventual convergence w.r.t. the running average. We obtain the first probabilistic bounds on the convergence time of bar{phi}(t) and precise bounds on the drift of TSS(t) that show that although TSS(t) eventually diverges, for a wide and interesting range of parameters, TSS(t) stays small for a number of rounds that is polynomial in the number of agents. Our results extend to the synchronous setting and settings where the agents are restricted to discrete values and perform rounding.
Cite as

Frederik Mallmann-Trenn, Yannic Maus, and Dominik Pajak. Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 148:1-148:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mallmanntrenn_et_al:LIPIcs.ICALP.2019.148,
  author =	{Mallmann-Trenn, Frederik and Maus, Yannic and Pajak, Dominik},
  title =	{{Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{148:1--148:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.148},
  URN =		{urn:nbn:de:0030-drops-107240},
  doi =		{10.4230/LIPIcs.ICALP.2019.148},
  annote =	{Keywords: population protocols, noisy communication, distributed averaging}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.159
Eigenvector Computation and Community Detection in Asynchronous Gossip Models

Authors: Frederik Mallmann-Trenn, Cameron Musco, and Christopher Musco

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We give a simple distributed algorithm for computing adjacency matrix eigenvectors for the communication graph in an asynchronous gossip model. We show how to use this algorithm to give state-of-the-art asynchronous community detection algorithms when the communication graph is drawn from the well-studied stochastic block model. Our methods also apply to a natural alternative model of randomized communication, where nodes within a community communicate more frequently than nodes in different communities. Our analysis simplifies and generalizes prior work by forging a connection between asynchronous eigenvector computation and Oja's algorithm for streaming principal component analysis. We hope that our work serves as a starting point for building further connections between the analysis of stochastic iterative methods, like Oja's algorithm, and work on asynchronous and gossip-type algorithms for distributed computation.
Cite as

Frederik Mallmann-Trenn, Cameron Musco, and Christopher Musco. Eigenvector Computation and Community Detection in Asynchronous Gossip Models. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 159:1-159:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{mallmanntrenn_et_al:LIPIcs.ICALP.2018.159,
  author =	{Mallmann-Trenn, Frederik and Musco, Cameron and Musco, Christopher},
  title =	{{Eigenvector Computation and Community Detection in Asynchronous Gossip Models}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{159:1--159:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.159},
  URN =		{urn:nbn:de:0030-drops-91639},
  doi =		{10.4230/LIPIcs.ICALP.2018.159},
  annote =	{Keywords: block model, community detection, distributed clustering, eigenvector computation, gossip algorithms, population protocols}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.34
How Large Is Your Graph?

Authors: Varun Kanade, Frederik Mallmann-Trenn, and Victor Verdugo

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
We consider the problem of estimating the graph size, where one is given only local access to the graph. We formally define a query model in which one starts with a seed node and is allowed to make queries about neighbours of nodes that have already been seen. In the case of undirected graphs, an estimator of Katzir et al. (2014) based on a sample from the stationary distribution pi uses O(1/||pi||_2 + d_avg) queries; we prove that this is tight. In addition, we establish this as a lower bound even when the algorithm is allowed to crawl the graph arbitrarily; the results of Katzir et al. give an upper bound that is worse by a multiplicative factor t_mix(1/n^4). The picture becomes significantly different in the case of directed graphs. We show that without strong assumptions on the graph structure, the number of nodes cannot be predicted to within a constant multiplicative factor without using a number of queries that are at least linear in the number of nodes; in particular, rapid mixing and small diameter, properties that most real-world networks exhibit, do not suffice. The question of interest is whether any algorithm can beat breadth-first search. We introduce a new parameter, generalising the well-studied conductance, such that if a suitable bound on it exists and is known to the algorithm, the number of queries required is sublinear in the number of edges; we show that this is tight.
Cite as

Varun Kanade, Frederik Mallmann-Trenn, and Victor Verdugo. How Large Is Your Graph?. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kanade_et_al:LIPIcs.DISC.2017.34,
  author =	{Kanade, Varun and Mallmann-Trenn, Frederik and Verdugo, Victor},
  title =	{{How Large Is Your Graph?}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.34},
  URN =		{urn:nbn:de:0030-drops-79767},
  doi =		{10.4230/LIPIcs.DISC.2017.34},
  annote =	{Keywords: Estimation, Random Walks, Social Networks}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.146
Bounds on the Voter Model in Dynamic Networks

Authors: Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, and Frederik Mallmann-Trenn

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
In the voter model, each node of a graph has an opinion, and in every round each node chooses independently a random neighbour and adopts its opinion. We are interested in the consensus time, which is the first point in time where all nodes have the same opinion. We consider dynamic graphs in which the edges are rewired in every round (by an adversary) giving rise to the graph sequence G_1, G_2, ..., where we assume that G_i has conductance at least phi_i. We assume that the degrees of nodes don't change over time as one can show that the consensus time can become super-exponential otherwise. In the case of a sequence of d-regular graphs, we obtain asymptotically tight results. Even for some static graphs, such as the cycle, our results improve the state of the art. Here we show that the expected number of rounds until all nodes have the same opinion is bounded by O(m/(d_{min}*phi)), for any graph with m edges, conductance phi, and degrees at least d_{min}. In addition, we consider a biased dynamic voter model, where each opinion i is associated with a probability P_i, and when a node chooses a neighbour with that opinion, it adopts opinion i with probability P_i (otherwise the node keeps its current opinion). We show for any regular dynamic graph, that if there is an epsilon > 0 difference between the highest and second highest opinion probabilities, and at least Omega(log(n)) nodes have initially the opinion with the highest probability, then all nodes adopt w.h.p. that opinion. We obtain a bound on the convergence time, which becomes O(log(n)/phi) for static graphs.
Cite as

Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, and Frederik Mallmann-Trenn. Bounds on the Voter Model in Dynamic Networks. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 146:1-146:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{berenbrink_et_al:LIPIcs.ICALP.2016.146,
  author =	{Berenbrink, Petra and Giakkoupis, George and Kermarrec, Anne-Marie and Mallmann-Trenn, Frederik},
  title =	{{Bounds on the Voter Model in Dynamic Networks}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{146:1--146:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.146},
  URN =		{urn:nbn:de:0030-drops-62901},
  doi =		{10.4230/LIPIcs.ICALP.2016.146},
  annote =	{Keywords: Voting, Distributed Computing, Conductance, Dynamic Graphs, Consensus}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.55
On the Voting Time of the Deterministic Majority Process

Authors: Dominik Kaaser, Frederik Mallmann-Trenn, and Emanuele Natale

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
In the deterministic binary majority process we are given a simple graph where each node has one out of two initial opinions. In every round, each node adopts the majority opinion among its neighbors. It is known that this process always converges in O(|E|) rounds to a two-periodic state in which every node either keeps its opinion or changes it in every round. It has been shown by Frischknecht, Keller, and Wattenhofer (2013) that the O(|E|) bound on the convergence time of the deterministic binary majority process is even for dense graphs tight. However, in many graphs such as the complete graph the process converges in just a constant number of rounds from any initial opinion assignment. We show that it is NP-hard to decide whether there exists an initial opinion assignment for which it takes more than k rounds to converge to the two-periodic stable state, for a given integer k. We then give a new upper bound on the voting time of the deterministic binary majority process. Our bound can be computed in linear time by carefully exploiting the structure of the potential function by Goles and Olivos. We identify certain modules of a graph G to obtain a new graph G^Delta. This new graph G^Delta has the property that the worst-case convergence time of G^Delta is an upper bound on that of G. Our new bounds asymptotically improve the best known bounds for various graph classes.
Cite as

Dominik Kaaser, Frederik Mallmann-Trenn, and Emanuele Natale. On the Voting Time of the Deterministic Majority Process. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kaaser_et_al:LIPIcs.MFCS.2016.55,
  author =	{Kaaser, Dominik and Mallmann-Trenn, Frederik and Natale, Emanuele},
  title =	{{On the Voting Time of the Deterministic Majority Process}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.55},
  URN =		{urn:nbn:de:0030-drops-64675},
  doi =		{10.4230/LIPIcs.MFCS.2016.55},
  annote =	{Keywords: distributed voting, majority rule}
}
  • Refine by Type
  • 17 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 9 2025
  • 1 2024
  • 1 2019
  • 1 2018
  • 1 2017
  • Show More...

  • Refine by Author
  • 9 Mallmann-Trenn, Frederik
  • 3 Berenbrink, Petra
  • 2 Giakkoupis, George
  • 2 Natale, Emanuele
  • 2 Starikovskaya, Tatiana
  • Show More...

  • Refine by Series/Journal
  • 17 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Distributed algorithms
  • 2 Mathematics of computing → Probabilistic algorithms
  • 2 Theory of computation → Random walks and Markov chains
  • 2 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 1 Applied computing → Systems biology
  • Show More...

  • Refine by Keyword
  • 2 Distributed Computing
  • 2 Plurality Consensus
  • 2 Random Walks
  • 2 population protocols
  • 1 Algorithms with Predictions
  • 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