Hot answers tagged


Addition and subtraction of binary numbers are in $\mathsf{AC^0}$. For any constant number $c$, $x \bmod c$ is $\mathsf{AC^0}$ reducible to division by $c$ ($\lfloor x/c \rfloor$): $$x \bmod c = x - (\overbrace{\lfloor x/c \rfloor + \cdots + \lfloor x/c \rfloor}^{c \text{ times}}) $$ It is known that $x \bmod c$ is hard for $\mathsf{AC^0}$ for any $c$ ...


$\def\ac{\mathrm{AC}^0}$Yes, $\ac\mathrm{PAD}=\mathrm{PPAD}$. (Here and below, I’m assuming $\ac$ is defined as a uniform class. Of course, with nonuniform $\ac$ we’d just get $\mathrm{PPAD/poly}$.) The basic idea is quite simple: $\ac$ can do one step of a Turing machine computation, hence we can simulate one polynomial-time computable edge by a ...


Although not exactly what you're looking for, this paper seems to be the most current (2019) efforts towards tight $AC^0[2]$ bounds as of yet, and provides a good summary of the difference between $AC^0$ and $AC^0[2]$ bounds.

Only top voted, non community-wiki answers of a minimum length are eligible