The class $ACC^0$ 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^0$.

A few years ago, Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach towards this conjecture. Torus polynomials approximate Boolean functions when the fractional part of their value on Boolean points is close to half the value of the function. They reduced the conjecture that $MAJORITY \notin ACC^0$ to a conjecture concerning the non-existence of low degree torus polynomials that approximate $MAJORITY$.

We reduce the non-existence problem further, to a statement about finding feasible solutions for an infinite family of linear programs. The main advantage of this statement is that it allows for incremental progress, which means finding feasible solutions for successively larger collections of these programs. As an immediate first step, we find feasible solutions for a large class of these linear programs, leaving only a finite set for further consideration. Our method is inspired by the method of dual polynomials, which is used to study the approximate degree of Boolean functions. Using our method, we also propose a way to progress further.

We prove several additional key results with the same method, which include:

1. A tight lower bound on the degree of symmetric torus polynomials that approximate the $AND$ function. As a consequence, we get a separation that symmetric torus polynomials are weaker than their asymmetric counterparts.

2. An error-degree trade-off for symmetric torus polynomials approximating $MAJORITY$, strengthening the corresponding result of Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019).

3. The first lower bounds against torus polynomials approximating $AND$, showcasing the power of the machinery we develop. This lower bound nearly matches the corresponding upper bound. Hence, we get an almost complete characterization of the torus polynomial approximation degree of $AND$.

4. Lower bounds against asymmetric torus polynomials approximating $MAJORITY$, or $AND$, in the very low error regime. This partially answers a question posed in Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) about error-reduction for torus polynomials.

Modified the set of results, changed the title, revised as per ITCS 2026 reviewer comments.

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.