Constraint Satisfaction Problems with Advice
<|reference_start|>Constraint Satisfaction Problems with Advice: 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.<|reference_end|>
@article{ghoshal2024constraint,
    title={Constraint Satisfaction Problems with Advice},
    author={Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev},
    journal={arXiv preprint arXiv:2403.02212},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.02212},
    primaryClass={cs.DS}
}