  The classical work of (Arora et al., 1999) provides a scheme that gives, for
any $\epsilon>0$, a polynomial time $1-\epsilon$ approximation algorithm for
dense instances of a family of $\mathcal{NP}$-hard problems, such as Max-CUT
and Max-$k$-SAT. In this paper we extend and speed up this scheme using a
logarithmic number of one-bit predictions. We propose a learning augmented
framework which aims at finding fast algorithms which guarantees approximation
consistency, smoothness and robustness with respect to the prediction error. We
provide such algorithms, which moreover use predictions parsimoniously, for
dense instances of various optimization problems.
