Degree Lower Bounds for Torus Polynomials and $MAJORITY$ vs $AC{C}^0$

Vaibhav Krishan, Sundar Vishwanathan

The class $AC{C}^0$ consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with $AND,NOT$ and $MO{D}_m$ gates, where $m$ is a natural number.…