  We revisit various PTAS's (Polynomial Time Approximation Schemes) for
minimization versions of dense problems, and show that they can be performed
with sublinear query complexity. This means that not only do we obtain a
(1+eps)-approximation to the NP-Hard problems in polynomial time, but also
avoid reading the entire input. This setting is particularly advantageous when
the price of reading parts of the input is high, as is the case, for examples,
where humans provide the input. Trading off query complexity with approximation
is the raison d'etre of the field of learning theory, and of the ERM (Empirical
Risk Minimization) setting in particular. A typical ERM result, however, does
not deal with computational complexity. We discuss two particular problems for
which (a) it has already been shown that sublinear querying is sufficient for
obtaining a (1 + eps)-approximation using unlimited computational power (an ERM
result), and (b) with full access to input, we could get a
(1+eps)-approximation in polynomial time (a PTAS). Here we show that neither
benefit need be sacrificed. We get a PTAS with efficient query complexity.
