EUVIMEDEUVIMED entdecken
Crossref

Testing Dependency of Weighted Random Graphs

Mor Oren-Loberman, Vered Paslev, Wasim Huleihel

IEEE Transactions on Information Theory · 2026-07 · 72 (7) · 5040-5058

DOI: 10.1109/tit.2026.3696669 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-07. Verfasst von Mor Oren-Loberman und 2 weiteren Autor:innen. Gefördert von: Israel Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this paper, we study the problem of testing for edge dependence between two weighted random graphs observed up to vertex relabeling. We formulate it as a binary hypothesis testing problem: under the null hypothesis, the two observed graphs are statistically independent, whereas under the alternative, the edges of one graph are correlated with the edges of a randomly vertex-permuted version of the other graph. For general edge-weight distributions, we establish thresholds at which optimal testing is information-theoretically impossible and possible, in terms of the number of vertices and the underlying weight distributions. Finally, we exhibit a statistical–computational gap for this problem and provide evidence that it is fundamental, using the low-degree polynomial framework.

Förderung

  • Israel Science Foundation

Zitieren

APA

Oren-Loberman, M., Paslev, V., & Huleihel, W. (2026). Testing Dependency of Weighted Random Graphs. IEEE Transactions on Information Theory, 72(7), 5040-5058. https://doi.org/10.1109/tit.2026.3696669

Vancouver

Oren-Loberman M, Paslev V, Huleihel W. Testing Dependency of Weighted Random Graphs. IEEE Transactions on Information Theory. 2026;72(7):5040-5058. doi:10.1109/tit.2026.3696669

BibTeX
@article{OrenLoberman2026,
  author = {Oren-Loberman, Mor and Paslev, Vered and Huleihel, Wasim},
  title = {Testing Dependency of Weighted Random Graphs},
  journal = {IEEE Transactions on Information Theory},
  year = {2026},
  volume = {72},
  number = {7},
  pages = {5040--5058},
  doi = {10.1109/tit.2026.3696669}
}
Kostenlos starten →