Zero-one laws for random feasibility problems

Perceptron problems are a class of random constraint satisfaction problems with geometric structure. They arise as fundamental models in fields as diverse as statistical physics, information theory, combinatorial optimization, and Banach geometry. We study the sharpness of the satisfiability threshold for perceptron problems. A line of recent works developed an extremely precise understanding of the "symmetric perceptron", a simple model with important applications. However, the techniques developed are delicate and highly reliant on the special structure of the problem.

Here, we consider a broad model of a random feasibility problem that encodes: the closest vector problem, linear feasibility, integer linear feasibility, perceptron problems, and combinatorial discrepancy in any norm. We define the "margin", which quantifies the (in)feasibility of such problems. Our main result is a set of sufficient conditions for the margin to concentrate. Concentration of the margin implies a host of new sharp threshold results in the mentioned models, and also simplifies and extends some key known results.