A review of the Statistical Mechanics approach to Random Optimization Problems <s> C. The perceptron problem continued: binary variables <s> This book contains a detailed and self-contained presentation of the replica theory of infinite range spin glasses. The authors also explain recent theoretical developments, paying particular attention to new applications in the study of optimization theory and neural networks. About two-thirds of the book are a collection of the most interesting and pedagogical articles on the subject. <s> BIB001 </s> A review of the Statistical Mechanics approach to Random Optimization Problems <s> C. The perceptron problem continued: binary variables <s> The use of randomness is now an accepted tool in Theoretical Computer Science but not everyone is aware of the underpinnings of this methodology in Combinatorics - particularly, in what is now called the probabilistic Method as developed primarily by Paul Erdoős over the past half century. Here I will explore a particular set of problems - all dealing with “good” colorings of an underlying set of points relative to a given family of sets. A central point will be the evolution of these problems from the purely existential proofs of Erdős to the algorithmic aspects of much interest to this audience. <s> BIB002
The binary perceptron problem consists in looking for solutions of (1) on the hypercube i.e. the domain of the variable σ is X N = {−1, +1} N instead of R N . This decision problem is NP-complete. Unfortunately Cover's calculation [6] cannot be extended to this case, though it is natural to expect a similar satisfiability threshold phenomenon at an a priori distinct value α s . Let us first try to study this point with basic probabilistic tools, namely the first and second moment method BIB002 . The former is an application of the Markov inequality, valid for positive integer valued random variables Z. We shall use it taking for Z the number of solutions of (1), where θ(x) = 1 if x > 0, 0 if x ≤ 0. The expectation value of the number of solutions is easily computed, with and vanishes when N → ∞ if α > 1. Hence, from Markov's inequality (6), with high probability constraints (1) have no solution on the hypercube when the ratio α exceeds unity: if the threshold α s exists, it must satisfy the bound α s ≤ 1. One can look for a lower bound to α s using the second moment method, relying on the inequality [13] The expectation value of the squared number of solutions reads since the vertices T a are chosen independently of each other. The expectation value on the right hand side of the above expression is simply the probability that the vector pointing to a randomly chosen vertex, T , has positive scalar product with both vectors σ, σ ′ . Elementary geometrical considerations reveal that where ϕ is the relative angle between the two vectors. This angle can be alternatively parametrized by the overlap between σ and σ ′ , i.e. the normalized scalar product, The last expression, in which I(E) denotes the indicator function of the event E, reveals the traduction between the concept of overlap and the more traditional Hamming distance. The sum over vectors in (10) can then be replaced by a sum over overlap values with appropriate combinatorial coefficients counting the number of pairs of vectors at a given overlap. The outcome is In the large N limit we can estimate this sum with the Laplace method, where Two conclusions can be drawn from the above calculation: • no useful lower bound to α s can be obtained from such a direct application of the second moment method. Indeed, maximization of G 2 (15) over q shows that 2 when N diverges, whenever α > 0, and in consequence the left hand side of (9) vanishes. A possible scenario which explains this absence of concentration of the number of solutions is the following. As shown by the moment calculation the natural scaling of Z is exponentially large in N (as is the total configuration space X N ). We shall thus denote s = (ln Z)/N the random variable of order one counting the log degeneracy of the solutions. Suppose s follows a large deviation principle  that we state in a very rough way as Prob [  , with L(s) a negative rate function, assumed for simplicity to be concave. Then the moments of Z are given, at the leading exponential order, by and are controlled by the values of s such that L ′ (s) = −n. The moments of larger and larger order n are thus dominated by the contribution of rarer and rarer instances with larger and larger numbers of solutions. On the contrary the typical value of the number of solutions is given by the maximum of L, reached in a value we denote s g (α): with high probability when N → ∞, Z is comprised between e N (sg(α)−ǫ) and e N (sg(α)+ǫ) , for any ǫ > 0. From this reasoning it appears that the relevant quantity to be computed is This idea of computing moments of vanishing order is known in statistical mechanics as the replica 1 method BIB001 . Its non-rigorous implementation consists in determining the moments of integer order n, which are then continued towards n = 0. The outcome of such a computation for the binary perceptron problem reads [15] s g (α) = max where Dz ≡ dz e is a decreasing function of α, which vanishes in α s ≃ 0.833. Numerical experiments support this value for the critical ratio of the satisfiable/unsatisfiable phase transition. • the calculation of the second moment is naturally related to the determination of the value of the overlap q between pairs of solutions (or equivalently their Hamming distance, recall Eq. (12)). This conclusion extends to the calculation of the n th moment for any integer n, and to the n → 0 limit. The value of q maximizing the r.h.s. of  , q * (α), represents the average overlap between two solutions of the same set of constraints BIB001 . Actually the distribution of overlaps is highly concentrated in the large N limit around q * (α), in other words the (reduced) Hamming distance between two solutions is, with high probability, equal to d Note that the perceptron problem is not as far as it could seem from the main subject of this review. There exists indeed a natural mapping between the binary perceptron problem and k-SAT. Assume the vertices T of the perceptron problem, instead of being drawn on the hypersphere, have coordinates that can take three values:  The scalar product is not required to be positive any longer, but to be larger than −(k − 1). It is an easy check that the perceptron problem admits a solution on the hypercube (σ i = ±1) if and only if F is satisfiable. While in the binary perceptron model all coordinates are non-vanishing, only a finite number of them take non zero values in k-SAT. For this reason k-SAT is called a diluted model in statistical physics. Also the direct application of the second moment method fails for the random k-SAT problem; yet a refined version of it was used in [11] , which leads to asymptotically (at large k) tight bounds on the location of the satisfiability threshold.