W. Krauth and &. Mézard, Storage capacity of memory networks with binary couplings, J. Phys. France, 1989.
URL : https://hal.archives-ouvertes.fr/jpa-00211124

L. H. Timothy, A. Watkin, M. Rau, and . Biehl, The statistical mechanics of learning a rule, Reviews of Modern Physics, vol.65, issue.2, p.499, 1993.

H. S. Seung, H. Sompolinsky, and N. Tishby, Statistical mechanics of learning from examples, Physical Review A, vol.45, issue.8, p.6056, 1992.

A. Engel and &. C. Van-den-broeck, Statistical mechanics of learning, 2001.

H. Nishimori, Statistical Physics of Spin Glasses and Information Processing: An Introduction, 2001.

M. Talagrand, Annals of mathematics, pp.221-263, 2006.

M. Talagrand, Spin glasses: a challenge for mathematicians: cavity and mean field models, vol.46, 2003.

M. Mézard and &. Montanari, Information, Physics, and Computation. Oxford Graduate Texts, 2009.

D. Achlioptas, A. Coja-oghlan, and F. Ricci-tersenghi, On the solution-space geometry of random constraint satisfaction problems, Random Structures & Algorithms, vol.38, issue.3, pp.251-268, 2011.

D. Panchenko, The Parisi formula for mixed p-spin models, The Annals of Probability, vol.42, issue.3, pp.946-958, 2014.

J. Ding, A. Sly, and N. Sun, Proof of the satisfiability conjecture for large k, Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp.59-68, 2015.

H. Jeong, J. Kim, and . Roche, Covering cubes by random half cubes, with applications to binary neural networks, Journal of Computer and System Sciences, vol.56, issue.2, pp.223-252, 1998.

M. Stojnic, , 2013.

J. Ding and N. Sun, Capacity lower bound for the Ising perceptron, 2018.

S. Franz, G. Parisi, M. Sevelev, P. Urbani, and F. Zamponi, Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems, SciPost Phys, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01569298

G. Parisi, Infinite number of order parameters for spin-glasses, Physical Review Letters, vol.43, issue.23, p.1754, 1979.

G. Parisi, A sequence of approximated solutions to the sk model for spin glasses, Journal of Physics A: Mathematical and General, vol.13, issue.4, p.115, 1980.

G. Parisi, The order parameter for spin glasses: a function on the interval 0-1, Journal of Physics A: Mathematical and General, vol.13, issue.3, p.1101, 1980.

. James, A problem in geometric probability, Math. Scand, vol.11, pp.109-111, 1962.

. Thomas-m-cover, Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition, IEEE transactions on electronic computers, issue.3, pp.326-334, 1965.

M. Shcherbina and B. Tirozzi, Rigorous solution of the Gardner problem, Communications in mathematical physics, vol.234, issue.3, pp.383-422, 2003.

M. Stojnic, Another look at the Gardner problem, 2013.

S. Franz and G. Parisi, The simplest model of jamming, Journal of Physics A: Mathematical and Theoretical, vol.49, issue.14, p.145001, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01281754

M. Stojnic, Negative spherical perceptron, 2013.

D. Achlioptas and C. Moore, The asymptotic order of the random k-SAT threshold, Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pp.779-788, 2002.

K. Y. Wong, &. Y. Kabashima, and H. Huang, Entropy landscape of solutions in the binary perceptron problem, Journal of Physics A: Mathematical and Theoretical, 2013.

H. Huang and Y. Kabashima, Origin of the computational hardness for learning with binary synapses, Physical Review E, vol.90, issue.5, p.52813, 2014.

L. Zdeborová and M. Mézard, Constraint satisfaction problems with isolated solutions are hard, Journal of Statistical Mechanics: Theory and Experiment, issue.12, p.12004, 2008.

A. Braunstein and R. Zecchina, Learning by message passing in networks of discrete synapses, Physical review letters, vol.96, issue.3, p.30201, 2006.

C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, and R. Zecchina, Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses, Physical review letters, vol.115, issue.12, p.128101, 2015.

C. Baldassi, C. Borgs, J. T. Chayes, A. Ingrosso, C. Lucibello et al., Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes, Proceedings of the National Academy of Sciences, vol.113, issue.48, pp.7655-7662, 2016.

L. Zdeborová and M. Mézard, Locked constraint satisfaction problems, Physical review letters, vol.101, issue.7, p.78702, 2008.

L. Zdeborová and F. Krzakala, Quiet planting in the locked constraint satisfaction problems, SIAM Journal on Discrete Mathematics, vol.25, issue.2, pp.750-770, 2011.

D. Achlioptas and A. Coja-oghlan, Algorithmic barriers from phase transitions, Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pp.793-802, 2008.

F. Krzakala and L. Zdeborová, Hiding quiet solutions in random constraint satisfaction problems, Physical review letters, vol.102, issue.23, p.238701, 2009.

E. Mossel, J. Neeman, and A. Sly, Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, vol.162, pp.431-461, 2015.

A. Coja-oghlan, F. Krzakala, W. Perkins, and L. Zdeborová, Information-theoretic thresholds from the cavity method, Advances in Mathematics, vol.333, pp.694-795, 2018.
URL : https://hal.archives-ouvertes.fr/cea-01448087

E. Friedgut, Sharp thresholds of graph properties, and the k-SAT problem, Journal of the American mathematical Society, vol.12, issue.4, pp.1017-1054, 1999.

. Oc-martin, O. Mézard, and . Rivoire, Frozen glass phase in the multi-index matching problem, Physical review letters, vol.93, issue.21, p.217205, 2004.

C. Schülke, Statistical physics of linear and bilinear inference problems, 2016.

J. R. De-almeida and D. Thouless, Stability of the Sherrington-Kirkpatrick solution of a spin glass model, J. Phys. A: Math. Gen, 1978.

&. M. Virasoro, M. Mézard, and G. Parisi, Spin glasses and beyond, World Science, 1987.

R. Monasson, Structural glass transition and the entropy of the metastable states, Physical Review Letter, 2847.

A. , General replica calculation

, Existence and stability of the RS fixed point (q0, ? q0) = (0, 0)