[1]   Emmanuel Abbe, Afonso S. Bandeira, Annina Bracher, and Amit Singer: Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery. To appear in the IEEE Transactions on Network Science and Engineering, 2014. [arXiv:1404.4749]

[2]   Emmanuel Abbe, Afonso S. Bandeira, Annina Bracher, and Amit Singer: Linear inverse problems on Erdös-Rényi graphs: Information-theoretic limits and efficient recovery. In IEEE Internat. Symp. on Information Theory (ISIT 2014), pp. 1251–1255, 2014. [doi:10.1109/ISIT.2014.6875033]

[3]   Emmanuel Abbe, Afonso S. Bandeira, and Georgina Hall: Exact recovery in the stochastic block model. 2014. [arXiv:1405.3267]

[4]   Emmanuel Abbe and Andrea Montanari: On the concentration of the number of solutions of random satisfiability formulas. Random Structures Algorithms, 45(3):362–382, 2014. [doi:10.1002/rsa.20501, arXiv:1006.3786v1]

[5]   Dimitris Achlioptas: Algorithmic barriers from phase transitions in graphs. In Graph Theoretic Concepts in Computer Science, volume 6410 of LNCS, pp. 1–1. Springer, 2010. Preliminary version in FOCS’08. [doi:10.1007/978-3-642-16926-7_1]

[6]   Dimitris Achlioptas, Haixia Jia, and Cristopher Moore: Hiding satisfying assignments: Two are better than one. J. Artif. Intell. Res. (JAIR), 24:623–639, 2005. Preliminary version in AAAI’04. [doi:10.1613/jair.1681]

[7]   Dimitris Achlioptas, Henry Kautz, and Bart Selman Carla Gomes: Generating satisfiable problem instances. In Proc. AAAI, pp. 256–261, 2000. Available at AAAI.

[8]   Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, and Prasad Tetali: Two-coloring random hypergraphs. Random Structures Algorithms, 20(2):249–259, 2002. [doi:10.1002/rsa.997]

[9]   Dimitris Achlioptas, Assaf Naor, and Yuval Peres: Rigorous Location of Phase Transitions in Hard Optimization Problems. Nature, 435(7043):759–764, 2005. [doi:10.1038/nature03602]

[10]   Fabrizio Altarelli, Remi Monasson, and Francesco Zamponi: Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for k-SAT at large clause-to-variable ratios. 2006. [arXiv:cs/0609101]

[11]   Kazuoki Azuma: Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, 19(3):357–367, 1967. [doi:10.2748/tmj/1178243286]

[12]   Wolfgang Barthel, Alexander K. Hartmann, Michele Leone, Federico Ricci-Tersenghi, Martin Weigt, and Riccardo Zecchina: Hiding solutions in random satisfiability problems: A statistical mechanics approach. Phys. Rev. Lett., 88(18):188701, 2002. [doi:10.1103/PhysRevLett.88.188701]

[13]   Mohsen Bayati, David Gamarnik, and Prasad Tetali: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. Ann. Probab., 41(6):4080–4115, 2013. Preliminary version in STOC’10. [doi:10.1214/12-AOP816]

[14]   Elwyn R. Berlekamp, Robert J. McEliece, and Henk C.A. Van Tilborg: On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Inform. Theory, 24(3):384–386, 1978. [doi:10.1109/TIT.1978.1055873]

[15]   Peter J. Bickel and Aiyou Chen: A nonparametric view of network models and newman-girvan and other modularities. Proceedings of the National Academy of Sciences, 106(50):21068–21073, 2009. [doi:10.1073/pnas.0907096106, ]

[16]   Andrej Bogdanov and Youming Qiao: On the security of Goldreich’s one-way function. Comput. Complexity, 21(1):83–127, 2012. Preliminary version in RANDOM’09. [doi:10.1007/s00037-011-0034-0]

[17]   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]

[18]   Amin Coja-Oghlan: Graph partitioning via adaptive spectral techniques. Combin. Probab. Comput., 19(2):227–284, 2010. [doi:10.1017/S0963548309990514]

[19]   Amin Coja-Oghlan: The asymptotic k-SAT threshold. In Proc. 46th STOC, pp. 804–813. ACM Press, 2014. ACM DL.

[20]   Amin Coja-Oghlan, Michael Krivelevich, and Dan Vilenchik: Why almost all satisfiable k-CNF formulas are easy. In Proc. 13th Int. Conf. Analysis of Algorithms (AofA’07), pp. 89–102, 2007. Available at DMTCS.

[21]   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]

[22]   Thomas M. Cover and Joy A. Thomas: Elements of Information Theory. Wiley Interscience, New York, 1991.

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

[24]   Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, and Michael Rink: Tight thresholds for cuckoo hashing via XORSAT. In Proc. 37th Internat. Colloq. on Automata, Languages and Programming (ICALP’10), pp. 213–225. Springer, 2010. [doi:10.1007/978-3-642-14165-2_19, arXiv:0912.0287]

[25]   Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, and Michael Rink: Tight thresholds for cuckoo hashing via XORSAT. 2010. [arXiv:0912.0287v1]

[26]   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. Preliminary version in FOCS’86. [doi:10.1016/0196-6774(89)90001-1]

[27]   Peter Elias: Coding for noisy channels. IRE Convention Record, 4:37–46, 1955.

[28]   Uriel Feige, Elchanan Mossel, and Dan Vilenchik: Complete convergence of message passing algorithms for some satisfiability problems. Theory of Computing, 9(19):617–651, 2013. Preliminary version in RANDOM’06. [doi:10.4086/toc.2013.v009a019]

[29]   Santo Fortunato: Community detection in graphs. Physics Reports, 486(3-5):75–174, 2010. [doi:10.1016/j.physrep.2009.11.002, arXiv:0906.0612]

[30]   Silvio Franz and Michele Leone: Replica bounds for optimization problems and diluted spin systems. J. Stat. Phys., 111(3-4):535, 2003. [doi:10.1023/A:1022885828956]

[31]   Silvio Franz, Michele Leone, and Fabio Lucio Toninelli: Replica bounds for diluted non-Poissonian spin systems. J. Phys. A, 36(43):10967, 2003. [doi:10.1088/0305-4470/36/43/021]

[32]   Ehud Friedgut: Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc., 12:1017–1054, 1999. Appendix by Jean Bourgain. [doi:10.1090/S0894-0347-99-00305-7]

[33]   Robert G. Gallager: Low-Density Parity-Check Codes. MIT Press, Cambridge, Massachussetts, 1963.

[34]    Anna Goldenberg, Alice X. Zheng, Stephen E. Fienberg, and Edoardo M. Airoldi: A survey of statistical network models. Foundations and Trends in Machine Learning, 2(2):129–233, 2010. [doi:10.1561/2200000005]

[35]   Oded Goldreich: In Candidate one-way functions based on expander graphs, volume 6650 of LNCS, pp. 76–87. Springer, 2011. [doi:10.1007/978-3-642-22670-0_10]

[36]   Francesco Guerra and Fabio Lucio Toninelli: The thermodynamic limit in mean field spin glasses. Commun. Math. Phys., 230(1):71–79, 2002. [doi:10.1007/s00220-002-0699-y]

[37]   Harri Haanpää, Matti Järvisalo, Petteri Kaski, and Ilkka Niemelä: Hard satisfiable clause sets for benchmarking equivalence reasoning techniques. Journal on Satisfiability, Boolean Modeling and Computation, 2(1-4):27–46, 2005. Available at JSAT.

[38]   Haixia Jia, Cristopher Moore, and Doug Strain: Generating hard satisfiable formulas by hiding solutions deceptively. J. Artif. Intell. Res. (JAIR), 28:107–118, 2007. Preliminary version in AAAI’05. [doi:10.1613/jair.2039, arXiv:cs/0503044]

[39]   Brian Karrer and Mark E.J. Newman: Stochastic blockmodels and community structure in networks. Phys. Rev. E, 83(1):016107, 2011. [doi:10.1103/PhysRevE.83.016107]

[40]   Florent Krzakala and Lenka Zdeborová: Hiding quiet solutions in random constraint satisfaction problems. Phys. Rev. Lett., 102(23):238701, 2009. [doi:10.1103/PhysRevLett.102.238701, arXiv:0901.2130]

[41]   Shrinivas Kudekar and Nicolas Macris: Sharp bounds for optimal decoding of Low-Density Parity-Check codes. IEEE Trans. Inform. Theory, 55(10):4635–4650, 2009. [doi:10.1109/TIT.2009.2027523, arXiv:0807.3065]

[42]   Raj Kumar, Krishna Kumar, Payam Pakzad, Amir Hesam Salavati, and Mohammad Amin Shokrollahi: Phase transitions for mutual information. In Turbo Codes and Iterative Information Processing (ISTC), 2010 6th International Symposium on, pp. 137–141, 2010.

[43]   John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira: Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. 18th Int. Conf. on Machine Learning (ICML’01), pp. 282–289, 2001. ACM DL.

[44]   Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, and Daniel A. Spielman: Efficient erasure correcting codes. IEEE Trans. Inform. Theory, 47(2):569–584, 2001. [doi:10.1109/18.910575]

[45]   Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman, and Volker Stemann: Practical loss-resilient codes. In Proc. 29th STOC, pp. 150–159. ACM Press, 1997. [doi:10.1145/258533.258573]

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

[47]   Andrea Montanari: Tight bounds for LDPC and LDGM codes under MAP decoding. IEEE Trans. Inform. Theory, 51(9):3221–3246, 2005. [doi:10.1109/TIT.2005.853320, arXiv:cs.IT/0407060]

[48]   Andrea Montanari: Estimating random variables from random sparse observations. European Transactions on Telecommunications, 19(4):385–403, 2008. ACM DL. [arXiv:0709.0145]

[49]   Andrea Montanari, Ricardo Restrepo, and Prasad Tetali: Reconstruction and Clustering in Random Constraint Satisfaction Problems. SIAM J. Discrete Math., 25(2):771–808, 2011. [doi:10.1137/090755862, arXiv:0904.2751]

[50]   Elchanan Mossel, Joe Neeman, and Allan Sly: Stochastic Block Models and Reconstruction. Prob. Theor. Rel. Fields, 2012. To appear. [arXiv:1202.1499]

[51]   Elchanan Mossel, Joe Neeman, and Allan Sly: A proof of the block model threshold conjecture. 2014. [arXiv:1311.4115]

[52]   Mark E. J. Newman: Communities, modules and large-scale structure in networks. Nature Physics, 8(1):25–31, 2011. [doi:10.1038/nphys2162]

[53]   Dmitry Panchenko and Michel Talagrand: Bounds for diluted mean-field spin glass models. Prob. Theor. Rel. Fields, 130(3):319–336, 2004. [doi:10.1007/s00440-004-0342-2]

[54]   George Polya and Gabor Szegö: Problems and Theorems in Analysis I. Springer, Berlin, 1998.

[55]   Tom Richardson and Rüdiger Urbanke: Modern Coding Theory. Cambridge Univ. Press, Cambridge, 2008.

[56]   Tom A.B. Snijders and Krzysztof Nowicki: Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure. Journal of Classification, 14(1):75–100, 1997. [doi:10.1007/s003579900004]

[57]   Endre Szemerédi: Regular partitions of graphs. Colloq. Internat. CNRS: Problèmes combinatoires et théorie des graphes, 260:399–401, 1978.

[58]   Lenka Zdeborová and Florent Krzakala: Quiet planting in the locked constraint satisfaction problems. SIAM J. Discrete Math., 25(2):750–770, 2011. [doi:10.1137/090750755, arXiv:0902.4185]