Strong freezing in the binary perceptron model

Source abstract

The binary perceptron model studies the set of solutions obtained by intersecting random Gaussian half-spaces with the discrete hypercube {-1,+1}^n. Pioneered in the work by Krauth and M{é}zard in the 1980s [KM89], one of the most striking physics predictions for this model is strong freezing, which says that typical solutions are isolated. Moreover, the conjecture was sharpened later to assert that typical solutions are at Hamming distance of order $n$ from every other solution [HWK13],[HK14]. This phenomenon has attracted a lot of attention over the years, partly due to its intricate connections to statistical physics and computational complexity. We prove that the binary perceptron model exhibits strong freezing with high probability at every fixed positive constraint density and every fixed margin. Our proof is based on the planted model and a restricted partition function that counts solutions having nonnegative overlap with the planted solution. Unlike the full partition function, this restricted one is monotone in the planted direction, so the FKG inequality decouples it from isolation, while the restriction costs only a factor of n+1. Together, these allow us to transfer the isolation of the planted solution to typical solutions, which completes the proof of strong freezing.