The class $ACC$ consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with $AND, NOT$ and $MOD_m$ gates, where $m$ is a natural number. At the frontier of our understanding lies a widely believed conjecture asserting that $MAJORITY$ does not belong to $ACC$. The Boolean function $MAJORITY$ outputs one if more than half of its inputs are one, and zero otherwise.
In a paper presented at ITCS 2019, Bhrushundi, Hosseini, Lovett and Rao reduced the conjecture that $MAJORITY \notin ACC$ to a conjecture concerning the non-existence of low degree torus polynomials that approximate $MAJORITY$. Torus polynomials approximate Boolean functions when the fractional part of their value on Boolean points is close to half the value of the function. Our contribution takes this a step further by reducing it to a seemingly more manageable conjecture regarding the $\ell^2$ norm of specific vectors. The crux of our work lies in constructing machinery inspired by the method of dual polynomials to establish lower bounds on the degree of torus polynomials approximating Boolean functions. Along the way, we prove several key results, which include:
1. A lower bound on the degree of symmetric torus polynomials approximating $\Delta_w$ functions, i.e., functions that output one if and only if there are exactly $w$ input variables that are one, which includes the $AND$ function. Consequently, we prove that asymmetric torus polynomials are strictly more powerful than their symmetric counterparts, addressing a question arising from Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019).
2. An error-degree trade-off for symmetric torus polynomials approximating $MAJORITY$, extending the corresponding result of Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019).
3. The existence of symmetric torus polynomials of degree at most half the number of variables, approximating $MAJORITY$ within inverse exponential error, when the number of variables is one more than a power of two. This surprising aspect of our machinery shows its versatility in proving upper bounds, despite being initially developed for lower bounds.
4. The first known lower bounds against asymmetric torus polynomials, showcasing the power of the machinery we develop. We prove that any torus polynomial approximating $AND$ within an error of $\frac{1}{2n}$ must have degree at least $\Omega(\log(n))$. Compare this with an upper bound of \(O(\log^2(n))\), which follows from Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019). Hence, we get an almost complete characterization of the torus polynomial approximation degree of $AND$.
5. Lower bounds against asymmetric torus polynomials approximating $MAJORITY$, or $AND$, in the very low error regime. Here, we prove that when the degree is one less than the number of variables, symmetric and asymmetric torus polynomials are equivalent in their power.
The machinery we have developed has significant room for further analysis, and leads to numerous open problems. There are various combinatorial questions, interesting in their own right, that also arise from our work.
Additionally, we apply our machinery to prove lower bounds on the degree of real polynomials approximating Boolean functions. We are able to prove strong lower bounds for a large set of functions with minimal effort.
