AC^0[p] Lower Bounds against MCSP via the Coin Problem

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal

Abstract

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an $n$-variate boolean function has circuit complexity less than a given parameter $s$. We prove that MCSP is hard for constant-depth circuits with mod $p$ gates, for any prime $p\geq 2$ (the circuit class $AC^0[p])$. Namely, we show that MCSP requires $d$-depth $AC^0[p]$ circuits of size at least $\exp(N^{0.49/d})$, where $N=2^n$ is the size of an input truth table of an $n$-variate boolean function. Our circuit lower bound proof shows that MCSP can solve the coin problem: distinguish uniformly random $N$-bit strings from those generated using independent samples from a biased random coin which is $1$ with probability $1/2+N^{-0.49}$, and $0$ otherwise. Solving the coin problem with such parameters is known to require exponentially large $AC^0[p]$ circuits. Moreover, this also implies that MAJORITY is computable by a non-uniform $AC^0$ circuit of polynomial size that also has MCSP-oracle gates. The latter has a few other consequences for the complexity of MCSP, e.g., we get that any boolean function in $NC^1$ (i.e., computable by a polynomial-size formula) can also be computed by a non-uniform polynomial-size $AC^0$ circuit with MCSP-oracle gates.

Versions