Sum-of-Squares Refutation Implies Planted Recovery for Semirandom CSPsResearch Paper
Random and semirandom constraint satisfaction problems (CSPs) are studied in two parallel lines of work. In refutation, the input is a CSP whose right-hand sides are random, and the task is to certify that no assignment satisfies much more than half of the constraints. In search, the input has a hidden planted assignment and the task is to recover it,…