Zero-One Laws for Random Feasibility Problems

Abstract

We introduce a general random model of a combinatorial optimization problem with geometric structure that encapsulates both linear programming and integer linear programming. Let $Q$ be a bounded set called the feasible set, $E$ be an arbitrary set called the constraint set, and $A$ be a random linear transform. We define and study the ${\ell }^q$-margin, $M_q:=d_q(AQ,E)$. The margin quantifies the feasibility of finding $y\in AQ$ satisfying the constraint $y\in E$. Our contribution is to establish strong concentration of the margin for any $q\in (2,\infty ]$, assuming only that $E$ has permutation symmetry. The case of $q=\infty$ is of particular interest in applications -- specifically to combinatorial ``balancing'' problems -- and is markedly out of the reach of the classical isoperimetric and concentration-of-measure tools that suffice for $q\le 2$. Generality is a key feature of this result: we assume permutation symmetry of the constraint set and nothing else. This allows us to encode many optimization problems in terms of the margin, including random versions of: the closest vector problem, integer linear feasibility, perceptron-type problems, ${\ell }^q$-combinatorial discrepancy for $2\le q\le \infty$, and matrix balancing. Concentration of the margin implies a host of new sharp threshold results in these models, and also greatly simplifies and extends some key known results.

arXiv commentRevisions. Typos fixed. Discussion around theorems 5 and 6 reworked