M2 course on "inference in large random graphs", Master program Mathématiques de l'Aléatoire, Université d'Orsay 

Lecture Notes

Slides 1, 2, 3, 4, 5, 6

Potential reads

• Hajek, S. Oh and J. Xu, “Minimax-optimal inference from partial rankings,” Neural Information brocessing Systems, (NIPS) 2014.
• Hajek, Y. Wu, and J. Xu, “Achieving exact cluster recovery threshold via semidefinite programming,” IEEE Transactions on Information Theory , vol. 62, May 2016, pp. 2788-2797. (Also Arxiv 1412.6156)
• Hajek, Y. Wu, and J. Xu, “Computational lower bounds for community detection on random graphs,” Proceedings Conf. on Learning Theory (COLT) June, 2015, Paris. Arxiv 1406.6625 poster slides
• Hajek and S. Sankagiri, “Recovering a Hidden Community in a Preferential Attachment Graph,” IEEE International Symposium on Information Theory, June 15-20, 2018, Vail, CO.) (Full version at Arxiv 1801.06818)

Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly

Yingjie Fei, Yudong Chen

https://arxiv.org/abs/1904.09635

Computationally efficient sparse clustering

Mathias Loffler, Alexander S. Wein, Afonso S. Bandeira

https://arxiv.org/pdf/2005.10817.pdf

Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality

Song Mei, Theodor Misiakiewicz, Andrea Montanari, Roberto I. Oliveira

https://arxiv.org/pdf/1703.08729.pdf

Testing for high-dimensional geometry in random graphs

Sébastien Bubeck, Jian Ding, Ronen Eldan, Mikl’os Z. R’acz

https://arxiv.org/pdf/1411.5713.pdf

‘On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors’

Andrea Montanari, Daniel Reichman, and Ofer Zeitouni,

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 63, NO. 3, MARCH 2017

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7779134

‘Information-theoretic thresholds for community detection in sparse networks.’

1. Banks, C. Moore, J. Neeman, and P. Netrapalli.

In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, pages 383?416, 2016.

http://proceedings.mlr.press/v49/banks16.pdf

A strengthening and a multipartite generalization of the Alon-Boppana-Serre Theorem,

1002. Mohar, https://arxiv.org/pdf/1002.1084.pdf

The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices

Florent Benaych-Georges (PMA, CMAP), Raj Rao Nadakuditi (EECS)

https://arxiv.org/abs/0910.2120

Approximating the cut-norm via Grothendieck’s inequality

Noga Alon and Assaf Naor, https://web.math.princeton.edu/~naor/homepage%20files/cutnorm.pdf

Spectral Techniques applied to sparse random graphs

1. Feige and E. Ofek

Wiley Interscience 2005, https://onlinelibrary.wiley.com/doi/epdf/10.1002/rsa.20089

‘Robust reconstruction on trees is determined by the second eigenvalue’.

1. Janson and E. Mossel.

The Annals of Probability, 32(3B):2630?2649, 2004

https://projecteuclid.org/download/pdfview_1/euclid.aop/1091813626

‘BROADCASTING ON TREES AND THE ISING MODEL’

William Evans, Claire Kenyon, Yuval Peres and Leonard J. Schulman

The Annals of Applied Probability, 2000, Vol. 10, No. 2, 410–433

https://projecteuclid.org/download/pdf_1/euclid.aoap/1019487349

Optimal Group Testing

Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Philipp Loick

Proceedings of COLT 2020

http://proceedings.mlr.press/v125/coja-oghlan20a/coja-oghlan20a.pdf

‘THE EIGENVALUES OF RANDOM SYMMETRIC MATRICES’

1. FÜREDI and J. KoMLóS

Combinatorica 1 (3) (1981) 233-241

https://faculty.math.illinois.edu/~z-furedi/PUBS/furedi_komlos_cca1981_random_eig.pdf