ECCC-Report TR19-133https://eccc.weizmann.ac.il/report/2019/133Comments and Revisions published for TR19-133en-usMon, 07 Oct 2019 19:08:01 +0300
Revision 1
| More on $AC^0[\oplus]$ and Variants of the Majority Function |
Nutan Limaye,
Srikanth Srinivasan,
Utkarsh Tripathi
https://eccc.weizmann.ac.il/report/2019/133#revision1In this paper we prove two results about $AC^0[\oplus]$ circuits.
We show that for $d(N) = o(\sqrt{\log N/\log \log N})$ and $N \leq s(N) \leq 2^{dN^{1/4d^2}}$ there is an explicit family of functions $\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$ such that
$f_N$ has uniform $AC^0$ formulas of depth $d$ and size at most $s$;
$f_N$ does not have $AC^0[\oplus]$ formulas of depth $d$ and size $s^{\varepsilon}$, where $\varepsilon$ is a fixed absolute constant.
This gives a quantitative improvement on the recent result of Limaye, Srinivasan, Sreenivasaiah, Tripathi, and Venkitesh, (STOC, 2019), which proved a similar Fixed-Depth Size-Hierarchy theorem but for $d \ll \log \log N$ and $s \ll \exp(N^{1/2^{\Omega(d)}})$.
As in the previous result, we use the Coin Problem to prove our hierarchy theorem. Our main technical result is the construction of uniform size-optimal formulas for solving the coin problem with improved sample complexity $(1/\delta)^{O(d)}$ (down from $(1/\delta)^{2^{O(d)}}$ in the previous result).
In our second result, we show that randomness buys depth in the $AC^0[\oplus]$ setting. Formally, we show that for any fixed constant $d\geq 2$, there is a family of Boolean functions that has polynomial-sized randomized uniform $AC^0$ circuits of depth $d$ but no polynomial-sized (deterministic) $AC^0[\oplus]$ circuits of depth $d$.
Previously Viola (Computational Complexity, 2014) showed that an increase in depth (by at least $2$) is essential to avoid superpolynomial blow-up while derandomizing randomized $AC^0$ circuits. We show that an increase in depth (by at least $1$) is essential even for $AC^0[\oplus]$.
As in Viola's result, the separating examples are promise variants of the Majority function on $N$ inputs that accept inputs of weight at least $N/2 + N/(\log N)^{d-1}$ and reject inputs of weight at most $N/2 - N/(\log N)^{d-1}$.
Mon, 07 Oct 2019 19:08:01 +0300https://eccc.weizmann.ac.il/report/2019/133#revision1
Paper TR19-133
| More on $AC^0[\oplus]$ and Variants of the Majority Function |
Utkarsh Tripathi,
Nutan Limaye,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2019/133In this paper we prove two results about $AC^0[\oplus]$ circuits.
We show that for $d(N) = o(\sqrt{\log N/\log \log N})$ and $N \leq s(N) \leq 2^{dN^{1/d^2}}$ there is an explicit family of functions $\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$ such that
$f_N$ has uniform $AC^0$ formulas of depth $d$ and size at most $s$;
$f_N$ does not have $AC^0[\oplus]$ formulas of depth $d$ and size $s^{\varepsilon}$, where $\varepsilon$ is a fixed absolute constant.
This gives a quantitative improvement on the recent result of Limaye, Srinivasan, Sreenivasaiah, Tripathi, and Venkitesh, (STOC, 2019), which proved a similar Fixed-Depth Size-Hierarchy theorem but for $d \ll \log \log N$ and $s \ll \exp(N^{1/2^{\Omega(d)}})$.
As in the previous result, we use the Coin Problem to prove our hierarchy theorem. Our main technical result is the construction of uniform size-optimal formulas for solving the coin problem with improved sample complexity $(1/\delta)^{d+4}$ (down from $(1/\delta)^{2^{O(d)}}$ in the previous result).
In our second result, we show that randomness buys depth in the $AC^0[\oplus]$ setting. Formally, we show that for any fixed constant $d\geq 2$, there is a family of Boolean functions that has polynomial-sized randomized uniform $AC^0$ circuits of depth $d$ but no polynomial-sized (deterministic) $AC^0[\oplus]$ circuits of depth $d$.
Previously Viola (Computational Complexity, 2014) showed that an increase in depth (by at least $2$) is essential to avoid superpolynomial blow-up while derandomizing randomized $AC^0$ circuits. We show that an increase in depth (by at least $1$) is essential even for $AC^0[\oplus]$.
As in Viola's result, the separating examples are promise variants of the Majority function on $N$ inputs that accept inputs of weight at least $N/2 + N/(\log N)^{d-1}$ and reject inputs of weight at most $N/2 - N/(\log N)^{d-1}$.
Wed, 02 Oct 2019 14:00:43 +0300https://eccc.weizmann.ac.il/report/2019/133