D. Achlioptas and A. Coja-oghlan, Algorithmic Barriers from Phase Transitions, 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp.793-802, 2008.
DOI : 10.1109/FOCS.2008.11
URL : http://arxiv.org/abs/0803.2122

D. Achlioptas and C. Moore, The Chromatic Number of Random Regular Graphs, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp.219-228, 2004.
DOI : 10.1007/978-3-540-27821-4_20

D. Achlioptas and A. Naor, The two possible values of the chromatic number of a random graph, Annals of Mathematics, vol.162, issue.3, pp.1335-1351, 2005.
DOI : 10.4007/annals.2005.162.1335

A. Victor-bapst, S. Coja-oghlan, F. Hetterich, D. Raßmann, and . Vilenchik, The Condensation Phase Transition in Random Graph Coloring, Communications in Mathematical Physics, vol.76, issue.26, pp.543-606, 2016.
DOI : 10.1007/s00220-015-2464-z

N. Biggs, Algebraic Potential Theory on Graphs, Bulletin of the London Mathematical Society, vol.29, issue.6, pp.641-682, 1997.
DOI : 10.1112/S0024609397003305

M. Bayati, M. Lelarge, and A. Montanari, Universality in polytope phase transitions and message passing algorithms, The Annals of Applied Probability, vol.25, issue.2, pp.753-822, 2015.
DOI : 10.1214/14-AAP1010
URL : https://hal.archives-ouvertes.fr/hal-01254901

[. Banks, C. Moore, J. Neeman, and P. Netrapalli, Informationtheoretic thresholds for community detection in sparse networks, 29th Annual Conference on Learning Theory, pp.383-416, 2016.

S. Boyd and L. Vandenberghe, Convex Optimization, 2004.

S. Chaiken, A Combinatorial Proof of the All Minors Matrix Tree Theorem, SIAM Journal on Algebraic Discrete Methods, vol.3, issue.3, pp.319-329, 1982.
DOI : 10.1137/0603033

A. Coja-oghlan, Random constraint satisfaction problems. arXiv preprint, 2009.
DOI : 10.4204/eptcs.9.4
URL : http://doi.org/10.4204/eptcs.9.4

A. Coja-oghlan, C. Efthymiou, and S. Hetterich, On the chromatic number of random regular graphs, Journal of Combinatorial Theory, Series B, vol.116, pp.367-439, 2016.
DOI : 10.1016/j.jctb.2015.09.006

A. Coja-oghlan and A. Frieze, Analyzing Walksat on Random Formulas, SIAM Journal on Computing, vol.43, issue.4, pp.1456-1485, 2014.
DOI : 10.1137/12090191X
URL : http://arxiv.org/abs/1106.0120

A. Coja-oghlan, A. Haqshenas, and S. Hetterich, Walksat stalls well below the satisfiability threshold, 2016.

A. Coja-oghlan, E. Mossel, and D. Vilenchik, A Spectral Approach to Analysing Belief Propagation for 3-Colouring, Combinatorics, Probability and Computing, vol.18, issue.06, pp.881-912, 2009.
DOI : 10.1007/s00493-006-0029-7

A. Coja-oghlan and W. Perkins, Belief propagation on replica symmetric random factor graph models. arXiv preprint, 2016.

[. Bruijn, Asymptotic Methods in Analysis, 1970.

D. Du and F. Hwang, Pooling Designs and Nonadaptive Group Testing: Important Tools for DNA Sequencing, 2006.
DOI : 10.1142/6122

L. David, A. Donoho, A. Javanmard, and . Montanari, Information-theoretically optimal compressed sensing via spatial coupling and approximate message passing, IEEE Transactions on Information Theory, vol.59, issue.11, pp.7434-7464, 2013.

V. Dani, C. Moore, and A. Olson, Tight Bounds on the Threshold for Permuted k-Colorability, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp.505-516, 2012.
DOI : 10.1007/978-3-642-32512-0_43

J. Ding, A. Sly, and N. Sun, Proof of the Satisfiability Conjecture for Large k, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '15, pp.59-68, 2015.
DOI : 10.1145/2746539.2746619

J. Ding, A. Sly, and N. Sun, Satisfiability Threshold for Random Regular nae-sat, Communications in Mathematical Physics, vol.5, issue.2, pp.435-489, 2016.
DOI : 10.1007/s00220-015-2492-8
URL : http://arxiv.org/abs/1310.4784

V. Feldman, W. Perkins, and S. Vempala, On the Complexity of Random Satisfiability Problems with Planted Solutions, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '15, pp.77-86, 2015.
DOI : 10.1145/2746539.2746577

M. Heo, R. L. Leibel, B. B. Boyer, W. K. Chung, M. Koulu et al., Pooling analysis of genetic data: The association of leptin receptor (LEPR) polymorphisms with variables related to human adiposity, Genetics, vol.159, issue.3, pp.1163-1178, 2001.

F. Krzakala, M. Mézard, and L. Zdeborová, Reweighted belief propagation and quiet planting for random K-SAT. arXiv preprint arXiv:1203, 2012.
URL : https://hal.archives-ouvertes.fr/hal-01087411

F. Krzakala and L. Zdeborová, Hiding Quiet Solutions in Random Constraint Satisfaction Problems, Physical Review Letters, vol.102, issue.23, p.238701, 2009.
DOI : 10.1103/PhysRevLett.102.238701

M. Mézard and C. Toninelli, Group Testing With Random Pools: Optimal Two-Stage Algorithms, IEEE Transactions on Information Theory, vol.57, issue.3, pp.1736-1745, 2011.
DOI : 10.1109/TIT.2010.2103752

]. R. Roc70, . Tyrrell-rockafellar-pak-sham, S. Joel, I. Bader, . Craig et al., Convex Analysis [SBC + 02 DNA pooling: a tool for large-scale association studies, Nature Reviews Genetics, vol.3, issue.11, pp.862-871, 1970.

A. Sly, N. Sun, and Y. Zhang, The number of solutions for random regular nae-sat. arXiv preprint, 2016.

T. Tanaka, A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors, IEEE Transactions on Information Theory, vol.48, issue.11, pp.2888-2910, 2002.
DOI : 10.1109/TIT.2002.804053

J. D. Vaaler, A geometric inequality with applications to linear forms, Pacific Journal of Mathematics, vol.83, issue.2, pp.543-553, 1979.
DOI : 10.2140/pjm.1979.83.543

I. Wang, . Shao-lun, K. Huang, K. Lee, and . Chen, Data extraction via histogram and arithmetic mean queries: Fundamental limits and algorithms, 2016 IEEE International Symposium on Information Theory (ISIT), pp.1386-1390, 2016.
DOI : 10.1109/ISIT.2016.7541526

Y. Wu and S. Verdú, Fundamental limits of almost lossless analog compression, 2009 IEEE International Symposium on Information Theory, pp.359-363, 2009.
DOI : 10.1109/ISIT.2009.5205734

K. Sh and . Zigangirov, Theory of Code Division Multiple Access Communication, 2004.

L. Zdeborová and F. Krzakala, Statistical physics of inference: Thresholds and algorithms. arXiv preprint, 2015.

[. Zhang, F. Krzakala, M. Mézard, and L. Zdeborová, Non-adaptive pooling strategies for detection of rare faulty items, 2013 IEEE International Conference on Communications Workshops (ICC), pp.1409-1414, 2013.
DOI : 10.1109/ICCW.2013.6649458