  We initiate the study of algorithms for constraint satisfaction problems with
ML oracle advice. We introduce two models of advice and then design
approximation algorithms for Max Cut, Max $2$-Lin, and Max $3$-Lin in these
models. In particular, we show the following.
  1. For Max-Cut and Max $2$-Lin, we design an algorithm that yields
near-optimal solutions when the average degree is larger than a threshold
degree, which only depends on the amount of advice and is independent of the
instance size. We also give an algorithm for nearly satisfiable Max $3$-Lin
instances with quantitatively similar guarantees.
  2. Further, we provide impossibility results for algorithms in these models.
In particular, under standard complexity assumptions, we show that Max $3$-Lin
is still $1/2 + \eta$ hard to approximate given access to advice, when there
are no assumptions on the instance degree distribution. Additionally, we also
show that Max $4$-Lin is $1/2 + \eta$ hard to approximate even when the average
degree of the instance is linear in the number of variables.
