= Two-threshold concentration for certifiable functions
{title2=$\Pr(Z\le a)\Pr(Z\ge b)\le\exp[-(b-a)^2/(4L^2rb)]$}
Suppose an integer-valued <certifiable function> is $L$-Lipschitz under one-coordinate changes and a value at least $b$ has a certificate of at most $rb$ coordinates. Any input with value at most $a<b$ must differ on at least $(b-a)/L$ certificate positions. Equal weights on those positions bound its <Talagrand convex distance> from the low-value event. Applying <Talagrand's convex distance inequality> gives the displayed product bound. For $0\le Z\le D$, median tails integrate to $|\mathbb EZ-\operatorname{med}Z|=O(L\sqrt{rD})$, and deviations of order $D$ have exponentially small probability.
Back to article page
