Optimizing a multilinear function over the vertices of the cube 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.)
 A: (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.
A: Let me know if I interpereted your question wrongly.
I have assumed the terms of $f$ have coefficients from $\{0,1\}.$
Your function
$f(x_1,\dots,x_n) = \sum_{(a_1,\dots,a_n) \in J} x_1^{a_1} \cdots x_n^{a_n}$ with $(a_1,\dots,a_n) \in \{0,1\}^n,$
where $J$ is a subset of $\{0,1\}^n$
can be rewritten as
$$
f(J;x_1,\dots,x_n) = \sum_{(a_1,\dots,a_n) \in J} (-1)^{a_1 x_1+ \cdots+ a_n x_n}=\\
 = \sum_{(a_1,\dots,a_n) \in \{0,1\}^n} \mathbf{1}\{(a_1,\ldots,a_n)\in J\}(-1)^{a_1 x_1+ \cdots+ a_n x_n}
$$
so it is essentially the Fourier (Walsh-Hadamard) transform (at 'frequency' $(x_1,\ldots,x_n)$) of the characteristic function of the set $J.$
i only considered the case when most coefficients are nonzero.
Assume that that the coefficients are $1$ except on the set $J^c=\{0,1\}^n \setminus J,$ which is much smaller than $2^n$ in size. You can consider the function
$f(J^c;x_1,\ldots,x_n)$ instead and write
$$
f(J;x_1,\ldots,x_n)=f(\{0,1\}^n;x_1,\ldots,x_n)-f(J^c;x_1,\ldots,x_n),
$$
and note that your $f$ is maximized when $f(J^c;x_1,\ldots,x_n)$ is minimized.
The full characteristic function for the space satisfies
$$
f(\{0,1\}^n;x_1,\ldots,x_n)=\left\{\begin{array}{ccl} 2^n, &\quad& (x_1,\ldots,x_n)=\mathbf{0},\\ 0, && else.\end{array} \right.
$$
since all nontrivial multilinear functions are balanced. This dominant maximum at zero is unlikely to be changed by the subtraction of $f(J^c;x_1,\ldots,x_n).$
If $\mathbf{0} \in J,$ as long as $\#J^c < 2^{n-1},$ you will have the maximum of $f(J;x_1,\ldots,x_n)$ be attained at $(x_1,\ldots,x_n)=\mathbb{0}.$ Typically this will hold even if $\#J^c>2^{n-1},$ since sums over $J^c$ will have some cancellation. You may be able to make this more precise, but I don't see a quick and easy way to consider this case when less than half the coefficients are nonzero.
In the former case you know the location of the maximum is at zero. Then you can evaluate $f(J^c;\mathbf{0})$ and subtract it from $2^n$ to obtain the actual maximum. Since this value could be negative, the maximum can actually be larger than $2^n.$
Note that in general you might think you can get a saving in computational complexity by evaluating the Fourier transform only on the frequencies in $J^c$ (or $J$) however removing some frequencies means you cannot directly use the fast kronecker product based transform computation which gives you all coefficients with complexity $O(n 2^n).$
