Quadratic polynomials of small modulus cannot represent OR

الأصل · EN

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 MODₘ 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 Ω((n)ᵒᵐ⁽¹⁾), and Barrington, Beigel, and Rudich established an upper bound of nᵒᵐ⁽¹⁾. 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≤ mᵒ⁽ᵈ⁾≤ mO(m), improving the previous best bound of 2ᵒ⁽ᵐ⁾ 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(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.