2 Search Results for "Ganassali, Luca"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.30
Algorithmic Contiguity from Low-Degree Conjecture and Applications in Correlated Random Graphs

Authors: Zhangsong Li

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

Abstract
In this paper, assuming a natural strengthening of the low-degree conjecture, we provide evidence of computational hardness for two problems: (1) the (partial) matching recovery problem in the sparse correlated Erdős-Rényi graphs G(n,q;ρ) when the edge-density q = n^{-1+o(1)} and the correlation ρ < √{α} lies below the Otter’s threshold, this resolves a remaining problem in [Jian Ding et al., 2023]; (2) the detection problem between a pair of correlated sparse stochastic block model S(n,λ/n;k,ε;s) and a pair of independent stochastic block models S(n,λs/n;k,ε) when ε² λ s < 1 lies below the Kesten-Stigum (KS) threshold and s < √α lies below the Otter’s threshold, this resolves a remaining problem in [Guanyi Chen et al., 2024]. One of the main ingredient in our proof is to derive certain forms of algorithmic contiguity between two probability measures based on bounds on their low-degree advantage. To be more precise, consider the high-dimensional hypothesis testing problem between two probability measures ℙ and ℚ based on the sample Y. We show that if the low-degree advantage Adv_{≤D}(dℙ/dℚ) = O(1), then (assuming the low-degree conjecture) there is no efficient algorithm A such that ℚ(A(Y) = 0) = 1-o(1) and ℙ(A(Y) = 1) = Ω(1). This framework provides a useful tool for performing reductions between different inference tasks.
Cite as

Zhangsong Li. Algorithmic Contiguity from Low-Degree Conjecture and Applications in Correlated Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{li:LIPIcs.APPROX/RANDOM.2025.30,
  author =	{Li, Zhangsong},
  title =	{{Algorithmic Contiguity from Low-Degree Conjecture and Applications in Correlated Random Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{30:1--30:18},
  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.30},
  URN =		{urn:nbn:de:0030-drops-243965},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.30},
  annote =	{Keywords: Algorithmic Contiguity, Low-degree Conjecture, Correlated Random Graphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.74
Correlation Detection in Trees for Planted Graph Alignment

Authors: Luca Ganassali, Laurent Massoulié, and Marc Lelarge

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Motivated by alignment of correlated sparse random graphs, we study a hypothesis problem of deciding whether two random trees are correlated or not. Based on this correlation detection problem, we propose MPAlign, a message-passing algorithm for graph alignment, which we prove to succeed in polynomial time at partial alignment whenever tree detection is feasible. As a result our analysis of tree detection reveals new ranges of parameters for which partial alignment of sparse random graphs is feasible in polynomial time. We conjecture that the connection between partial graph alignment and tree detection runs deeper, and that the parameter range where tree detection is impossible, which we partially characterize, corresponds to a region where partial graph alignment is hard (not polytime feasible).
Cite as

Luca Ganassali, Laurent Massoulié, and Marc Lelarge. Correlation Detection in Trees for Planted Graph Alignment. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 74:1-74:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ganassali_et_al:LIPIcs.ITCS.2022.74,
  author =	{Ganassali, Luca and Massouli\'{e}, Laurent and Lelarge, Marc},
  title =	{{Correlation Detection in Trees for Planted Graph Alignment}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{74:1--74:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.74},
  URN =		{urn:nbn:de:0030-drops-156709},
  doi =		{10.4230/LIPIcs.ITCS.2022.74},
  annote =	{Keywords: inference on graphs, hypothesis testing, Erd\H{o}s-R\'{e}nyi random graphs}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2022

  • Refine by Author
  • 1 Ganassali, Luca
  • 1 Lelarge, Marc
  • 1 Li, Zhangsong
  • 1 Massoulié, Laurent

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Hypothesis testing and confidence interval computation
  • 1 Mathematics of computing → Max marginal computation
  • 1 Mathematics of computing → Random graphs
  • 1 Theory of computation → Random network models

  • Refine by Keyword
  • 1 Algorithmic Contiguity
  • 1 Correlated Random Graphs
  • 1 Erdős-Rényi random graphs
  • 1 Low-degree Conjecture
  • 1 hypothesis testing
  • 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