Sharp threshold for the Ising perceptron model

Abstract

Consider the discrete cube {−1,1}N and a random collection of half spaces which includes each half space H(x):={y∈{−1,1}N:x·y≥κ N} for x∈{−1,1}N independently with probability p. Is the intersection of these half spaces empty? This is called the Ising perceptron model under Bernoulli disorder. We prove that this event has a sharp threshold, that is, the probability that the intersection is empty increases quickly from ϵ to 1−ϵ when p increases only by a factor of 1+o(1) as N→∞.