Suppose I have $n$ Boolean variables $x\_1,\dots,x\_n$, and an objective function of the form $f(x\_1,\dots,x\_n) = \sum\_{a\_1,\dots,a\_n}c\_{a\_1,\dots,a\_n} x\_1^{a\_1} \cdots x\_n^{a\_n}$ with $(a\_1,\dots,a\_n) \in \{0,1\}^n$. I know this is a bit vague, but suppose that there aren't that many nonvanishing coefficients and/or all the nonvanishing terms are of low degree. I want to maximize $f$ over $(x\_1,\dots,x\_n) \in \{+1,-1\}^n$. How hard is it? (If no coefficients vanish, then checking all $2^n$ vertices wouldn't take that much more time than writing down all $2^n$ coefficients.)



Optimizing a multilinear function over the vertices of the cube
(Making a CW answer to take this off the list of unanswered questions.)


As noted in comments by Jason Gaitonde, MAXCUT for a graph $G=(V,E)$ is equivalent to maximization of the quadratic multilinear polynomial
$$-\sum\_{(i,j)\in E}x\_ix\_j$$
over $\{-1,1\}^V$, hence the problem is NP-hard.


