[1]   Emmanuel Abbe, Afonso S. Bandeira, and Georgina Hall: Exact recovery in the stochastic block model. IEEE Trans. Inform. Theory, 62(1):471–487, 2016. [doi:10.1109/TIT.2015.2490670, arXiv:1405.3267]

[2]   David Aldous and John M. Steele: The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures, pp. 1–72. Springer, 2004. [doi:10.1007/978-3-662-09444-0_1]

[3]   Sanjeev Arora, Satish Rao, and Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):5:1–5:37, 2009. Preliminary version in STOC’04. [doi:10.1145/1502793.1502794]

[4]   Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann, and Dan Vilenchik: The condensation phase transition in random graph coloring. Communications in Mathematical Physics, 341(2):543–606, 2016. Preliminary version in RANDOM’14. [doi:10.1007/s00220-015-2464-z, arXiv:1404.5513]

[5]   Béla Bollobás and Alex D. Scott: Max cut for random graphs with a planted partition. Combin. Probab. Comput., 13(4-5):451–474, 2004. [doi:10.1017/S0963548304006303]

[6]   Ravi B. Boppana: Eigenvalues and graph bisection: An average-case analysis. In Proc. 28th FOCS, pp. 280–285. IEEE Comp. Soc. Press, 1987. [doi:10.1109/SFCS.1987.22]

[7]   Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, and Michael Sipser: Graph bisection algorithms with good average case behavior. Combinatorica, 7(2):171–191, 1987. Preliminary version in FOCS’84. [doi:10.1007/BF02579448]

[8]   Ted Carson and Russell Impagliazzo: Hill-climbing finds random planted bisections. In Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’01), pp. 903–909. ACM Press, 2001. ACM DL.

[9]   Amin Coja-Oghlan: A spectral heuristic for bisecting random graphs. Random Structures Algorithms, 29(3):351–398, 2006. Preliminary version in SODA’05. [doi:10.1002/rsa.20116]

[10]   Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch: How does the core sit inside the mantle? Electronic Notes in Discrete Mathematics, 49:489 – 496, 2015. [doi:10.1016/j.endm.2015.06.068, arXiv:1503.09030]

[11]   Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch: The minimum bisection in the planted bisection model. In Proc. 19th Internat. Workshop on Randomization and Computation (RANDOM’15), pp. 710–725. Schloss Dagstuhl, 2015. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.710, arXiv:1505.02985]

[12]   Anne Condon and Richard M. Karp: Algorithms for graph partitioning on the planted partition model. Random Structures Algorithms, 18(2):116–140, 2001. Preliminary version in RANDOM’99. [doi:10.1002/1098-2418(200103)18:2¡116::AID-RSA1001¿3.0.CO;2-2]

[13]   Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová: Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6):066106, 2011. [doi:10.1103/PhysRevE.84.066106, arXiv:1109.3041]

[14]   Amir Dembo, Andrea Montanari, and Subhabrata Sen: Extremal cuts of sparse random graphs. Ann. Probab., 45(2):1190–1217, 2017. [doi:10.1214/15-AOP1084, arXiv:1503.03923]

[15]   Tassos Dimitriou and Russell Impagliazzo: Go with the winners for graph bisection. In Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’98), pp. 510–520. ACM Press, 1998. ACM DL.

[16]   Martin E. Dyer and Alan M. Frieze: The solution of some random NP-hard problems in polynomial expected time. J. Algorithms, 10(4):451–489, 1989. [doi:10.1016/0196-6774(89)90001-1]

[17]   Uriel Feige and Joe Kilian: Heuristics for semirandom graph problems. J. Comput. System Sci., 63(4):639–671, 2001. [doi:10.1006/jcss.2001.1773]

[18]   Uriel Feige and Robert Krauthgamer: A polylogarithmic approximation of the minimum bisection. SIAM J. Comput., 31(4):1090–1118, 2002. Preliminary version in FOCS’00. See also SIAM Rev. 2006. [doi:10.1137/S0097539701387660]

[19]   Uriel Feige and Eran Ofek: Spectral techniques applied to sparse random graphs. Random Structures Algorithms, 27(2):251–275, 2005. [doi:10.1002/rsa.20089]

[20]   Joel Friedman, Jeff Kahn, and Endre Szemerédi: On the second eigenvalue of random regular graphs. In Proc. 21st STOC, pp. 587–598. ACM Press, 1989. [doi:10.1145/73007.73063]

[21]   Michael R. Garey, David S. Johnson, and Larry J. Stockmeyer: Some simplified NP-complete graph problems. Theoret. Comput. Sci., 1(3):237–267, 1976. Preliminary version in STOC’74. [doi:10.1016/0304-3975(76)90059-1]

[22]    Michel X. Goemans and David P. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, 1995. Preliminary version in STOC’94. [doi:10.1145/227683.227684]

[23]   Paul W. Holland, Kathryn Laskey, and Samuel Leinhardt: Stochastic blockmodels: First steps. Social networks, 5(2):109–137, 1983. [doi:10.1016/0378-8733(83)90021-7]

[24]   Morteza Ibrahimi, Yash Kanoria, Matt Kraning, and Andrea Montanari: The set of solutions of random XORSAT formulae. Ann. Appl. Probab., 25(5):2743–2808, 2015. Preliminary version in SODA’12. [doi:10.1214/14-AAP1060, arXiv:1107.5377]

[25]   Svante Janson, Tomasz Łuczak, and Andrzej Ruciński: Random Graphs. John Wiley & Sons, 2000. [doi:10.1002/9781118032718]

[26]   Mark Jerrum and Gregory B. Sorkin: The Metropolis algorithm for graph bisection. Discrete Applied Mathematics, 82(1-3):155–175, 1998. [doi:10.1016/S0166-218X(97)00133-9]

[27]   Ari Juels: Topics in black-box combinatorial function optimization. Ph. D. thesis, UC Berkeley, 1996. Available at Research Gate.

[28]   Richard Karp: Reducibility among combinatorial problems. In Complexity of Computer Computations, pp. 85–103. Plenum Press, 1972. [doi:10.1007/978-1-4684-2001-2_9]

[29]   Marek Karpinski: Approximability of the minimum bisection problem: An algorithmic challenge. In Proc. 27th Internat. Symp. Math. Found. Comput. Sci. (MFCS’02), volume 2420 of LNCS, pp. 59–67. Springer, 2002. [doi:10.1007/3-540-45687-2_4]

[30]   Subhash Khot: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput., 36(4):1025–1071, 2006. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447037]

[31]   Luděk Kučera: Expected complexity of graph partitioning problems. Discr. Appl. Math., 57(2-3):193–212, 1995. [doi:10.1016/0166-218X(94)00103-K]

[32]   Malwina J. Luczak and Colin McDiarmid: Bisecting sparse random graphs. Random Structures Algorithms, 18(1):31–38, 2001. [doi:10.1002/1098-2418(200101)18:1¡31::AID-RSA3¿3.0.CO;2-1]

[33]   Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan: Approximation algorithms for semi-random partitioning problems. In Proc. 44th STOC, pp. 367–384. ACM Press, 2012. [doi:10.1145/2213977.2214013, arXiv:1205.2234]

[34]   Laurent Massoulié: Community detection thresholds and the weak Ramanujan property. In Proc. 46th STOC, pp. 694–703. ACM Press, 2014. [doi:10.1145/2591796.2591857, arXiv:1311.3085]

[35]   Frank McSherry: Spectral partitioning of random graphs. In Proc. 42nd FOCS, pp. 529–537. IEEE Comp. Soc. Press, 2001. [doi:10.1109/SFCS.2001.959929]

[36]   Marc Mézard and Andrea Montanari: Information, Physics, and Computation. Oxford Univ. Press, 2009. [doi:10.1093/acprof:oso/9780198570837.001.0001]

[37]   Elchanan Mossel, Joe Neeman, and Allan Sly: Stochastic block models and reconstruction, 2012. [arXiv:1202.1499]

[38]   Elchanan Mossel, Joe Neeman, and Allan Sly: Consistency thresholds for the planted bisection model. In Proc. 47th STOC, pp. 69–75. ACM Press, 2015. [doi:10.1145/2746539.2746603, arXiv:1407.1591]

[39]   Elchanan Mossel, Joe Neeman, and Allan Sly: Belief propagation, robust reconstruction and optimal recovery of block models. Ann. Appl. Probab., 26(4):2211–2256, 2016. Preliminary version in COLT’14. [doi:10.1214/15-AAP1145, arXiv:1309.1380]

[40]   Elchanan Mossel, Joe Neeman, and Allan Sly: A proof of the block model threshold conjecture. Combinatorica, pp. 1–44, 2017. [doi:10.1007/s00493-016-3238-8, arXiv:1311.4115]

[41]   Ralph Neininger and Ludger Rüschendorf: A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab., 14(1):378–418, 2004. [doi:10.1214/aoap/1075828056]

[42]   Harald Räcke: Optimal hierarchical decompositions for congestion minimization in networks. In Proc. 40th STOC, pp. 255–264. ACM Press, 2008. [doi:10.1145/1374376.1374415]

[43]   Michel Talagrand: The Parisi formula. Ann. Math., 163(1):221–263, 2006. [doi:10.4007/annals.2006.163.221]

[44]   Van H. Vu: Spectral norm of random matrices. Combinatorica, 27(6):721–736, 2007. Preliminary version in STOC’05. [doi:10.1007/s00493-007-2190-z]