They say a little ways down: > there are classical optimization problems whose values can be approximated in sublinear time This can actually be quite useful

They say a little ways down: > there are classical optimization problems whose values can be approximated in sublinear time This can actually be quite useful if the approximation is guaranteed, or even if it isn't, as long as it works well in practice. https://en.wikipedia.org/wiki/Hardness_of_approximation https://en.wikipedia.org/wiki/Hardness_of_approximation