We prove that all functions that have low degree torus polynomials approximating them with small error also have $MidBit^+$ circuits computing them. This serves as a partial converse to the result that all $ACC$ functions have low degree torus polynomials approximating them with small error, by Bhrushundi, Hosseini, Lovett and ... more >>>

We give a conversion from non-classical polynomials to $\mathit{MidBit}^+$ circuits and vice-versa. This conversion, along with previously known results, shows that torus polynomials, non-classical polynomials and $\mathit{MidBit}^+$ circuits can all be converted to each other. Therefore lower bounds against any of these models lead to lower bounds against all three ... more >>>

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 ... more >>>

We explore the torus polynomial approximation based approach towards a long-standing question: whether AND can be computed by $CC^0$ circuits - the class of constant-depth polynomial size circuits containing $MOD_m$ gates for some natural number $m$.
Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach ... more >>>