Certifiable function

An integer-valued function $f$ is $g$-certifiable when every input $x$ with $f(x)=k$ has a set of at most $g(k)$ coordinates whose values alone guarantee that $f\ge k$.

The entropy method for certifiable functions turns short certificates into bounds on coordinate sensitivity. Suppose a nonnegative integer-valued certifiable function $f$ changes by at most $L$ when one coordinate changes and has certificates of size at most $g(k)$ at value $k$. Define the coordinate-deleted functionsassuming these functions are measurable. At an input of value $k$, changing a coordinate outside a chosen certificate cannot reduce the value below $k$. Hence $f_i=f$ outside that certificate, while $0\le f-f_i\le L$ on it. ConsequentlyFor independent random variables, the Efron–Stein inequality already gives $\mathrm{Var}(f(X))\le L^2\mathbb{E}g(f(X))$. When $L=1$ and $g(k)=k$, the stronger bound ${\sum }_i(f-f_i)\le f$ makes $f$ a self-bounding function. Tensorization of entropy and a modified logarithmic Sobolev inequality control exponential rather than quadratic variation, producing concentration inequalities. The certificate size alone needs this coordinate-change bound; an arbitrarily large change in one coordinate is not controlled by a short certificate.