Two-threshold concentration for certifiable functions ($\mathrm{Pr}(Z\le a)\mathrm{Pr}(Z\ge b)\le \exp [-(b-a{)}^2/(4L^{2}rb)]$)

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{E}Z-\mathrm{med}Z|=O(L\sqrt{rD})$, and deviations of order $D$ have exponentially small probability.