Search Results

Documents authored by Prałat, Paweł

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.28
The Stochastic Block Model Has the Overlap Graph Property for Modularity

Authors: Shankar Bhamidi, David Gamarnik, Remco van der Hofstad, Nelly Litvak, Paweł Prałat, Fiona Skerman, and Yasmin Tousinejad

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to coincide with conjectured algorithmic limits in problems with statistical computational gap. We consider the Stochastic Block Model (SBM), where the graph has a planted partition with k equal-size blocks which form the "communities", and where, for parameters p > q, vertices within the same community connect with probability p, while vertices in different communities connect with probability q, independently across pairs of vertices. Modularity-based clustering algorithms have become ubiquitous in applications. This article studies theoretical limits of local algorithms based on the modularity score on the SBM. We establish that modularity exhibits OGP on the SBM. This rules out a class of local algorithms based on modularity for recovery in the SBM, and shows slow mixing time for a related Markov Chain. Theoretically this is one of the few instances where OGP has been established for a "planted" model, as most such analyses to date consider the "null" model. As part of our analysis, we extend a result by Bickel and Chen 2009, who established that with high probability, the modularity optimal partition of SBM is o(n) local moves away from the planted partition, where n is the graph size. We show that, with high probability, any partition with modularity score sufficiently near the optimal value is close to the planted partition.
Cite as

Shankar Bhamidi, David Gamarnik, Remco van der Hofstad, Nelly Litvak, Paweł Prałat, Fiona Skerman, and Yasmin Tousinejad. The Stochastic Block Model Has the Overlap Graph Property for Modularity. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhamidi_et_al:LIPIcs.ICALP.2026.28,
  author =	{Bhamidi, Shankar and Gamarnik, David and van der Hofstad, Remco and Litvak, Nelly and Pra{\l}at, Pawe{\l} and Skerman, Fiona and Tousinejad, Yasmin},
  title =	{{The Stochastic Block Model Has the Overlap Graph Property for Modularity}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.28},
  URN =		{urn:nbn:de:0030-drops-264177},
  doi =		{10.4230/LIPIcs.ICALP.2026.28},
  annote =	{Keywords: community detection, average-case complexity, overlap gap property, modularity, Louvain, stochastic block model}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.114
Canonical Labelling of Random Regular Graphs

Authors: Mikhail Isaev, Tamás Makai, Brendan D. McKay, Paweł Prałat, Jane Tan, and Maksim Zhukovskii

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We prove that whenever d = d(n) → ∞ and n-d → ∞ as n → ∞, then with high probability for any non-trivial initial colouring, the colour refinement algorithm distinguishes all vertices of the random regular graph 𝒢_{n,d}. This, in particular, implies that with high probability 𝒢_{n,d} admits a canonical labelling computable in time O(min{n^ω, nd²+ndlog n}), where ω < 2.372 is the matrix multiplication exponent.
Cite as

Mikhail Isaev, Tamás Makai, Brendan D. McKay, Paweł Prałat, Jane Tan, and Maksim Zhukovskii. Canonical Labelling of Random Regular Graphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 114:1-114:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{isaev_et_al:LIPIcs.ICALP.2026.114,
  author =	{Isaev, Mikhail and Makai, Tam\'{a}s and McKay, Brendan D. and Pra{\l}at, Pawe{\l} and Tan, Jane and Zhukovskii, Maksim},
  title =	{{Canonical Labelling of Random Regular Graphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{114:1--114:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.114},
  URN =		{urn:nbn:de:0030-drops-265039},
  doi =		{10.4230/LIPIcs.ICALP.2026.114},
  annote =	{Keywords: random graphs, regular graphs, colour refinement, canonical labelling, graph isomorphism}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.5
Asynchronous Majority Dynamics on Binomial Random Graphs

Authors: Divyarthi Mohan and Paweł Prałat

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

Abstract
We study information aggregation in networks when agents interact to learn a binary state of the world. Initially each agent privately observes an independent signal which is correct with probability 1/2+δ for some δ > 0. At each round, a node is selected uniformly at random to update their public opinion to match the majority of their neighbours (breaking ties in favour of their initial private signal). Our main result shows that for sparse and connected binomial random graphs G(n,p) the process stabilizes in a correct consensus in 𝒪(nlog² n/log log n) steps with high probability. In fact, when log n/n ≪ p = o(1) the process terminates at time T^ = (1+o(1))nlog n, where T^ is the first time when all nodes have been selected at least once. However, in dense binomial random graphs with p = Ω(1), there is an information cascade where the process terminates in the incorrect consensus with probability bounded away from zero.
Cite as

Divyarthi Mohan and Paweł Prałat. Asynchronous Majority Dynamics on Binomial Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mohan_et_al:LIPIcs.APPROX/RANDOM.2024.5,
  author =	{Mohan, Divyarthi and Pra{\l}at, Pawe{\l}},
  title =	{{Asynchronous Majority Dynamics on Binomial Random Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.5},
  URN =		{urn:nbn:de:0030-drops-209985},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.5},
  annote =	{Keywords: Opinion dynamics, Social learning, Stochastic processes, Random Graphs, Consensus}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.29
A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process

Authors: Pu Gao, Calum MacRury, and Paweł Prałat

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

Abstract
The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamiltonian cycle in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves it in α n rounds, where α < 2.01678 is derived from the solution to some system of differential equations. We also show that the player cannot achieve the desired property in less than β n rounds, where β > 1.26575. These results improve the previously best known bounds and, as a result, the gap between the upper and lower bounds is decreased from 1.39162 to 0.75102.
Cite as

Pu Gao, Calum MacRury, and Paweł Prałat. A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.APPROX/RANDOM.2022.29,
  author =	{Gao, Pu and MacRury, Calum and Pra{\l}at, Pawe{\l}},
  title =	{{A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{29:1--29:22},
  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.29},
  URN =		{urn:nbn:de:0030-drops-171517},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.29},
  annote =	{Keywords: Random graphs and processes, Online adaptive algorithms, Hamiltonian cycles, Differential equation method}
}
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