Boundaries of majority function approximation using torus polynomials
Majority and Torus Polynomials: Bounded-Lift Lower Bounds and Explicit Constructions
Computational Complexity
Summary
This paper explores limits on how well certain polynomials called torus polynomials can approximate the majority function, which decides if most inputs are ones or zeros. The authors show that if these polynomials use only small integer shifts, they must have high complexity. They also build explicit polynomials that approximate any Boolean function exactly or with very small error. These findings help understand fundamental challenges in computational complexity and could guide future design of algorithms.
What this means in practice
- •For circuit designers: Avoid designing low-degree polynomials with limited integer shifts to approximate majority functions efficiently.
- •For cryptography engineers: Use explicit torus polynomial constructions to model Boolean functions with guaranteed approximation error bounds.
A theory result. No direct application yet.
Authors
Saint Wesonga
Abstract
Bhrushundi et al. (2019) introduced torus polynomial approximation as an approach to separating Majority from $ACC^0$. In this model, approximation is measured modulo integers. Krishan and Vishwanathan (2026) developed a duality framework for lower bounds and posed five open problems. We resolve two of these, concerning integer lifts and explicit polynomial approximations. An integer lift records the integer shifts that turn a torus approximation into an ordinary real approximation. We show that a degree-d torus polynomial approximating Majority with error at most 1/8 and lift contained in an interval of width $B$ must satisfy $d(B + 1) = Ω(n)$. This rules out low-degree approximating polynomials with lifts in {-1, 0, 1}, answering their Open Problem 2. We also answer Open Problem 5 by giving, for every Boolean function on $n \geq 1$ variables, an explicit torus polynomial approximation of degree at most $n - 1$. Its error is optimal: zero when the accepting set has even cardinality and $2^{-n-1}$ otherwise. The results presented were discovered and formalized in Lean using GPT-6 Astra.