  We consider the problem of approximately solving constraint satisfaction
problems with arity $k > 2$ ($k$-CSPs) on instances satisfying certain
expansion properties, when viewed as hypergraphs. Random instances of $k$-CSPs,
which are also highly expanding, are well-known to be hard to approximate using
known algorithmic techniques (and are widely believed to be hard to approximate
in polynomial time). However, we show that this is not necessarily the case for
instances where the hypergraph is a high-dimensional expander.
  We consider the spectral definition of high-dimensional expansion used by
Dinur and Kaufman [FOCS 2017] to construct certain primitives related to PCPs.
They measure the expansion in terms of a parameter $\gamma$ which is the
analogue of the second singular value for expanding graphs. Extending the
results by Barak, Raghavendra and Steurer [FOCS 2011] for 2-CSPs, we show that
if an instance of MAX k-CSP over alphabet $[q]$ is a high-dimensional expander
with parameter $\gamma$, then it is possible to approximate the maximum
fraction of satisfiable constraints up to an additive error $\epsilon$ using
$q^{O(k)} \cdot (k/\epsilon)^{O(1)}$ levels of the sum-of-squares SDP
hierarchy, provided $\gamma \leq \epsilon^{O(1)} \cdot (1/(kq))^{O(k)}$.
  Based on our analysis, we also suggest a notion of threshold-rank for
hypergraphs, which can be used to extend the results for approximating 2-CSPs
on low threshold-rank graphs. We show that if an instance of MAX k-CSP has
threshold rank $r$ for a threshold $\tau = (\epsilon/k)^{O(1)} \cdot
(1/q)^{O(k)}$, then it is possible to approximately solve the instance up to
additive error $\epsilon$, using $r \cdot q^{O(k)} \cdot (k/\epsilon)^{O(1)}$
levels of the sum-of-squares hierarchy. As in the case of graphs,
high-dimensional expanders (with sufficiently small $\gamma$) have threshold
rank 1 according to our definition.
