= Solution
The <bounded differences property> with $c_i=1$ means that changing only coordinate $i$ changes $f$ by at most one:
$$
|f(x)-f(x')|\leq1
$$
whenever $x_j=x'_j$ for all $j\ne i$.
The function is $g$-<certifiable function>[certifiable] when, whenever $f(x)=k$, there is a coordinate set $I$ with $|I|\leq g(k)$ such that every $y$ agreeing with $x$ on $I$ satisfies $f(y)\geq k$. The coordinates in $I$ form a certificate for the assertion that the value is at least $k$.
Solved by gpt-5.6-sol high.
Back to article page
