2015/09/29 by Holden Lee, Lee, Holden
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1509.08896
openalex publication_date 2015/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 MODm 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 Ω((log n)Om(1)), and Barrington, Beigel, and Rudich established an upper bound of nOm(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≤ mO(d)≤ mO(log m), improving the previous best bound of 2O(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.