  We present an efficient algorithm to solve semirandom planted instances of
any Boolean constraint satisfaction problem (CSP). The semirandom model is a
hybrid between worst-case and average-case input models, where the input is
generated by (1) choosing an arbitrary planted assignment $x^*$, (2) choosing
an arbitrary clause structure, and (3) choosing literal negations for each
clause from an arbitrary distribution "shifted by $x^*$" so that $x^*$
satisfies each constraint. For an $n$ variable semirandom planted instance of a
$k$-arity CSP, our algorithm runs in polynomial time and outputs an assignment
that satisfies all but a $o(1)$-fraction of constraints, provided that the
instance has at least $\tilde{O}(n^{k/2})$ constraints. This matches, up to
$polylog(n)$ factors, the clause threshold for algorithms that solve fully
random planted CSPs [FPV15], as well as algorithms that refute random and
semirandom CSPs [AOW15, AGK21]. Our result shows that despite having worst-case
clause structure, the randomness in the literal patterns makes semirandom
planted CSPs significantly easier than worst-case, where analogous results
require $O(n^k)$ constraints [AKK95, FLP16].
  Perhaps surprisingly, our algorithm follows a significantly different
conceptual framework when compared to the recent resolution of semirandom CSP
refutation. This turns out to be inherent and, at a technical level, can be
attributed to the need for relative spectral approximation of certain random
matrices - reminiscent of the classical spectral sparsification - which ensures
that an SDP can certify the uniqueness of the planted assignment. In contrast,
in the refutation setting, it suffices to obtain a weaker guarantee of absolute
upper bounds on the spectral norm of related matrices.
