  An open problem in complexity theory is to find the minimal degree of a
polynomial representing the $n$-bit OR function modulo composite $m$. This
problem is related to understanding the power of circuits with $\text{MOD}_m$
gates where $m$ is composite. The OR function is of particular interest because
it is the simplest function not amenable to bounds from communication
complexity. Tardos and Barrington established a lower bound of $\Omega((\log
n)^{O_m(1)})$, and Barrington, Beigel, and Rudich established an upper bound of
$n^{O_m(1)}$. No progress has been made on closing this gap for twenty years,
and progress will likely require new techniques.
  We make progress on this question viewed from a different perspective: rather
than fixing the modulus $m$ and bounding the minimum degree $d$ in terms of the
number of variables $n$, we fix the degree $d$ and bound $n$ in terms of the
modulus $m$. For degree $d=2$, we prove a quasipolynomial bound of $n\le
m^{O(d)}\le m^{O(\log m)}$, improving the previous best bound of $2^{O(m)}$
implied by Tardos and Barrington's general bound.
  To understand the computational power of quadratic polynomials modulo $m$, we
introduce a certain dichotomy which may be of independent interest. Namely, we
define a notion of boolean rank of a quadratic polynomial $f$ and relate it to
the notion of diagonal rigidity. Using additive combinatorics, we show that
when the rank is low, $f(\mathbf x)=0$ must have many solutions. Using
techniques from exponential sums, we show that when the rank of $f$ is high,
$f$ is close to equidistributed. In either case, $f$ cannot represent the OR
function in many variables.

Computational Complexity