Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 208 / 3 / a

The bounded differences property with $c_i=1$ means that changing only coordinate $i$ changes $f$ by at most one:whenever $x_j=x_j^{\prime }$ for all $j\ne i$.

The function is $g$-certifiable when, whenever $f(x)=k$, there is a coordinate set $I$ with $|I|\le g(k)$ such that every $y$ agreeing with $x$ on $I$ satisfies $f(y)\ge k$. The coordinates in $I$ form a certificate for the assertion that the value is at least $k$.