  We consider multilinear Littlewood polynomials, polynomials in $n$ variables
in which a specified set of monomials $U$ have $\pm 1$ coefficients, and all
other coefficients are $0$. We provide upper and lower bounds (which are close
for $U$ of degree below $\log n$) on the minimum, over polynomials $h$
consistent with $U$, of the maximum of $|h|$ over $\pm 1$ assignments to the
variables. (This is a variant of a question posed by Erd\"os regarding the
maximum on the unit disk of univariate polynomials of given degree with unit
coefficients.) We outline connections to the theory of quasi-random graphs and
hypergraphs, and to statistical mechanics models. Our methods rely on the
analysis of the Gale-Berlekamp game; on the constructive side of the generic
chaining method; on a Khintchine-type inequality for polynomials of degree
greater than $1$; and on Bernstein's approximation theory inequality.
