7 Search Results for "Kiwi, Marcos"

Document
DOI: 10.4230/LIPIcs.STACS.2026.11
The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs

Authors: Zylan Benjert, Kostas Lakis, Johannes Lengler, and Raghu Raman Ravi

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

Abstract
We prove that the diameter of threshold (zero temperature) Geometric Inhomogeneous Random Graphs (GIRG) is asymptotically almost surely Θ(log n). This has strong implications for the runtime of many distributed protocols on those graphs, which often have runtimes bounded as a function of the diameter. The GIRG model exhibits many properties empirically found in real-world networks, and the runtime of various practical algorithms has empirically been found to scale in the same way for GIRG and for real-world networks, in particular related to computing distances, diameter, clustering, cliques and chromatic numbers. Thus the GIRG model is a promising candidate for deriving insight about the performance of algorithms in real-world instances. The diameter was previously only known in the one-dimensional case, and the proof relied very heavily on dimension one. Our proof employs a similar Peierls-type argument alongside a novel renormalization scheme. Moreover, instead of using topological arguments (which become complicated in high dimensions) in establishing the connectivity of certain boundaries, we employ some comparatively recent and clearer graph-theoretic machinery. The lower bound is proven via a simple ad-hoc construction.
Cite as

Zylan Benjert, Kostas Lakis, Johannes Lengler, and Raghu Raman Ravi. The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{benjert_et_al:LIPIcs.STACS.2026.11,
  author =	{Benjert, Zylan and Lakis, Kostas and Lengler, Johannes and Ravi, Raghu Raman},
  title =	{{The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{11:1--11:21},
  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.11},
  URN =		{urn:nbn:de:0030-drops-255009},
  doi =		{10.4230/LIPIcs.STACS.2026.11},
  annote =	{Keywords: GIRG, Diameter, Distributed Algorithms, Complex Networks}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.14
Energy-Efficient Maximal Independent Sets in Radio Networks

Authors: Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, and Gopal Pandurangan

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

Abstract
The maximal independent set (MIS) is one of the most fundamental problems in distributed computing, and it has been studied intensively for over four decades. This paper focuses on the MIS problem in the radio network model, a standard model widely used to model wireless networks, particularly ad hoc wireless and sensor networks. Energy is a premium resource in these networks, which are typically battery-powered. Hence, designing distributed algorithms that use as little energy as possible is crucial. We use the well-established energy model where a node can be sleeping or awake in a round, and only the awake rounds (when it can send or listen) determine the energy complexity of the algorithm, which we want to minimize. We present new, more energy-efficient MIS algorithms in radio networks with arbitrary and unknown graph topology. We present algorithms for two popular variants of the radio model - with collision detection (CD) and without collision detection (no-CD). Specifically, we obtain the following results: 1) CD model: We present a randomized distributed MIS algorithm with energy complexity O(log n), round complexity O(log² n), and failure probability 1 / poly(n), where n is the network size. We show that our energy complexity is optimal by showing a matching Ω(log n) lower bound. 2) no-CD model: In the more challenging no-CD model, we present a randomized distributed MIS algorithm with energy complexity O(log²n log log n), round complexity O(log³ n log Δ), and failure probability 1 / poly(n). The energy complexity of our algorithm is significantly lower than the round (and energy) complexity of O(log³ n) of the best known distributed MIS algorithm of Davies [PODC 2023] for arbitrary graph topology.
Cite as

Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, and Gopal Pandurangan. Energy-Efficient Maximal Independent Sets in Radio Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banasik_et_al:LIPIcs.DISC.2025.14,
  author =	{Banasik, Dominick and Dani, Varsha and Dufoulon, Fabien and Gupta, Aayush and Hayes, Thomas P. and Pandurangan, Gopal},
  title =	{{Energy-Efficient Maximal Independent Sets in Radio Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{14:1--14: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.14},
  URN =		{urn:nbn:de:0030-drops-248311},
  doi =		{10.4230/LIPIcs.DISC.2025.14},
  annote =	{Keywords: Distributed Computing, Energy Complexity, Sleeping Model, Radio Networks, Maximal Independent Set}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.9
Synchronous Versus Asynchronous Tile-Based Self-Assembly

Authors: Florent Becker, Phillip Drake, Matthew J. Patitz, and Trent A. Rogers

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
In this paper we study the relationship between mathematical models of tile-based self-assembly which differ in terms of the synchronicity of tile additions. In the standard abstract Tile Assembly Model (aTAM), each step of assembly consists of a single tile being added to an assembly. At any given time, each location on the perimeter of an assembly to which a tile can legally bind is called a frontier location, and for each step of assembly one frontier location is randomly selected and a tile is added. In the Synchronous Tile Assembly Model (syncTAM), at each step of assembly every frontier location simultaneously receives a tile. Our results show that while directed, non-cooperative syncTAM systems are capable of universal computation (while directed, non-cooperative aTAM systems are known not to be), and they are capable of building shapes that can't be built within the aTAM, the non-cooperative aTAM is also capable of building shapes that can't be built within the syncTAM even cooperatively. We show a variety of results that demonstrate the similarities and differences between these two models.
Cite as

Florent Becker, Phillip Drake, Matthew J. Patitz, and Trent A. Rogers. Synchronous Versus Asynchronous Tile-Based Self-Assembly. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.DNA.31.9,
  author =	{Becker, Florent and Drake, Phillip and Patitz, Matthew J. and Rogers, Trent A.},
  title =	{{Synchronous Versus Asynchronous Tile-Based Self-Assembly}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.9},
  URN =		{urn:nbn:de:0030-drops-238580},
  doi =		{10.4230/LIPIcs.DNA.31.9},
  annote =	{Keywords: self-assembly, noncooperative self-assembly, models of computation, tile assembly systems}
}
Document
DOI: 10.4230/LIPIcs.WABI.2025.17
An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT

Authors: Ahsan Sanaullah, Degui Zhi, and Shaojie Zhang

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
String matching problems in bioinformatics are typically for finding exact substring matches between a query and a reference text. Previous formulations often focus on maximum exact matches (MEMs). However, multiple occurrences of substrings of the query in the text that are long enough but not maximal may not be captured by MEMs. Such long matches can be informative, especially when the text is a collection of similar sequences such as genomes. In this paper, we describe a new type of match between a pattern and a text that aren't necessarily maximal in the query, but still contain useful matching information: locally maximal exact matches (LEMs). There are usually a large amount of LEMs, so we only consider those above some length threshold ℒ. These are referred to as long LEMs. The purpose of long LEMs is to capture substring matches between a query and a text that are not necessarily maximal in the pattern but still long enough to be important. Therefore efficient long LEMs finding algorithms are desired for these datasets. However, these datasets are too large to query on traditional string indexes. Fortunately, these datasets are very repetitive. Recently, compressed string indexes that take advantage of the redundancy in the data but retain efficient querying capability have been proposed as a solution. We therefore give an efficient algorithm for computing all the long LEMs of a query and a text in a BWT runs compressed string index. We describe an O(m+occ) expected time algorithm that relies on an O(r) words space string index for outputting all long LEMs of a pattern with respect to a text given the matching statistics of the pattern with respect to the text. Here m is the length of the query, occ is the number of long LEMs outputted, and r is the number of runs in the BWT of the text. The O(r) space string index we describe relies on an adaptation of the move data structure by Nishimoto and Tabei. We are able to support LCP[i] queries in constant time given SA[i]. In other words, we answer PLCP[i] queries in constant time. These PLCP queries enable the efficient long LEM query. Long LEMs may provide useful similarity information between a pattern and a text that MEMs may ignore. This information is particularly useful in pangenome and biobank scale haplotype panel contexts.
Cite as

Ahsan Sanaullah, Degui Zhi, and Shaojie Zhang. An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sanaullah_et_al:LIPIcs.WABI.2025.17,
  author =	{Sanaullah, Ahsan and Zhi, Degui and Zhang, Shaojie},
  title =	{{An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{17:1--17:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.17},
  URN =		{urn:nbn:de:0030-drops-239433},
  doi =		{10.4230/LIPIcs.WABI.2025.17},
  annote =	{Keywords: BWT, LEM, Long LEM, MEM, Run Length Compressed BWT, Move Data Structure, Pangenome}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.10
Biased Linearity Testing in the 1% Regime

Authors: Subhash Khot and Kunal Mittal

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We study linearity testing over the p-biased hypercube ({0,1}ⁿ, μ_p^{⊗n}) in the 1% regime. For a distribution ν supported over {x ∈ {0,1}^k:∑_{i=1}^k x_i = 0 (mod 2)}, with marginal distribution μ_p in each coordinate, the corresponding k-query linearity test Lin(ν) proceeds as follows: Given query access to a function f:{0,1}ⁿ → {-1,1}, sample (x_1,… ,x_k)∼ ν^{⊗n}, query f on x_1,… ,x_k, and accept if and only if ∏_{i ∈ [k]} f(x_i) = 1. Building on the work of Bhangale, Khot, and Minzer (STOC '23), we show, for 0 < p ≤ 1/2, that if k ≥ 1+1/p, then there exists a distribution ν such that the test Lin(ν) works in the 1% regime; that is, any function f:{0,1}ⁿ → {-1,1} passing the test Lin(ν) with probability ≥ 1/2+ε, for some constant ε > 0, satisfies Pr_{x∼μ_p^{⊗n}}[f(x) = g(x)] ≥ 1/2+δ, for some linear function g, and a constant δ = δ(ε) > 0. Conversely, we show that if k < 1+1/p, then no such test Lin(ν) works in the 1% regime. Our key observation is that the linearity test Lin(ν) works if and only if the distribution ν satisfies a certain pairwise independence property.
Cite as

Subhash Khot and Kunal Mittal. Biased Linearity Testing in the 1% Regime. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{khot_et_al:LIPIcs.CCC.2025.10,
  author =	{Khot, Subhash and Mittal, Kunal},
  title =	{{Biased Linearity Testing in the 1\% Regime}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{10:1--10:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.10},
  URN =		{urn:nbn:de:0030-drops-237046},
  doi =		{10.4230/LIPIcs.CCC.2025.10},
  annote =	{Keywords: Linearity test, 1\% regime, p-biased}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.13
Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring

Authors: Samuel Baguley, Yannic Maus, Janosch Ruff, and George Skretas

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Hyperbolic random graphs inherit many properties that are present in real-world networks. The hyperbolic geometry imposes a scale-free network with a strong clustering coefficient. Other properties like a giant component, the small world phenomena and others follow. This motivates the design of simple algorithms for hyperbolic random graphs. In this paper we consider threshold hyperbolic random graphs (HRGs). Greedy heuristics are commonly used in practice as they deliver a good approximations to the optimal solution even though their theoretical analysis would suggest otherwise. A typical example for HRGs are degeneracy-based greedy algorithms [Bläsius, Fischbeck; Transactions of Algorithms '24]. In an attempt to bridge this theory-practice gap we characterise the parameter of degeneracy yielding a simple approximation algorithm for colouring HRGs. The approximation ratio of our algorithm ranges from (2/√3) to 4/3 depending on the power-law exponent of the model. We complement our findings for the degeneracy with new insights on the clique number of hyperbolic random graphs. We show that degeneracy and clique number are substantially different and derive an improved upper bound on the clique number. Additionally, we show that the core of HRGs does not constitute the largest clique. Lastly we demonstrate that the degeneracy of the closely related standard model of geometric inhomogeneous random graphs behaves inherently different compared to the one of hyperbolic random graphs.
Cite as

Samuel Baguley, Yannic Maus, Janosch Ruff, and George Skretas. Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baguley_et_al:LIPIcs.STACS.2025.13,
  author =	{Baguley, Samuel and Maus, Yannic and Ruff, Janosch and Skretas, George},
  title =	{{Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.13},
  URN =		{urn:nbn:de:0030-drops-228386},
  doi =		{10.4230/LIPIcs.STACS.2025.13},
  annote =	{Keywords: hyperbolic random graphs, scale-free networks, power-law graphs, cliques, degeneracy, vertex colouring, chromatic number}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.30
Cover and Hitting Times of Hyperbolic Random Graphs

Authors: Marcos Kiwi, Markus Schepers, and John Sylvester

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

Abstract
We study random walks on the giant component of Hyperbolic Random Graphs (HRGs), in the regime when the degree distribution obeys a power law with exponent in the range (2,3). In particular, we focus on the expected times for a random walk to hit a given vertex or visit, i.e. cover, all vertices. We show that up to multiplicative constants: the cover time is n(log n)², the maximum hitting time is nlog n, and the average hitting time is n. The first two results hold in expectation and a.a.s. and the last in expectation (with respect to the HRG). We prove these results by determining the effective resistance either between an average vertex and the well-connected "center" of HRGs or between an appropriately chosen collection of extremal vertices. We bound the effective resistance by the energy dissipated by carefully designed network flows associated to a tiling of the hyperbolic plane on which we overlay a forest-like structure.
Cite as

Marcos Kiwi, Markus Schepers, and John Sylvester. Cover and Hitting Times of Hyperbolic Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kiwi_et_al:LIPIcs.APPROX/RANDOM.2022.30,
  author =	{Kiwi, Marcos and Schepers, Markus and Sylvester, John},
  title =	{{Cover and Hitting Times of Hyperbolic Random Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.30},
  URN =		{urn:nbn:de:0030-drops-171523},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.30},
  annote =	{Keywords: Random walk, hyperbolic random graph, cover time, hitting time, average hitting time, target time, effective resistance, Kirchhoff index}
}
  • Refine by Type
  • 7 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 1 2022

  • Refine by Author
  • 1 Baguley, Samuel
  • 1 Banasik, Dominick
  • 1 Becker, Florent
  • 1 Benjert, Zylan
  • 1 Dani, Varsha
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Random network models
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Stochastic processes
  • 1 Theory of computation → Computational complexity and cryptography
  • Show More...

  • Refine by Keyword
  • 1 1% regime
  • 1 BWT
  • 1 Complex Networks
  • 1 Diameter
  • 1 Distributed Algorithms
  • 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