Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-133 | 7th October 2019 19:08

More on $AC^0[\oplus]$ and Variants of the Majority Function

RSS-Feed




Revision #1
Authors: Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi
Accepted on: 7th October 2019 19:08
Downloads: 14
Keywords: 


Abstract:

In 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}$.



Changes to previous version:

Many typos and minor errors corrected.


Paper:

TR19-133 | 2nd October 2019 02:22

More on $AC^0[\oplus]$ and Variants of the Majority Function





TR19-133
Authors: Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi
Publication: 2nd October 2019 14:00
Downloads: 75
Keywords: 


Abstract:

In 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}$.



ISSN 1433-8092 | Imprint