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 TR23-045 | 25th May 2023 13:04

Tight Correlation Bounds for Circuits Between AC0 and TC0

RSS-Feed




Revision #1
Authors: Vinayak Kumar
Accepted on: 25th May 2023 13:04
Downloads: 310
Keywords: 


Abstract:

We initiate the study of generalized $AC^0$ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight $\ge k$ (up to negations of the input bits), which we denote $GC^0(k)$. The gate set of this class includes biased LTFs like the $k$-$OR$ (outputs $1$ iff $\ge k$ bits are $1$) and $k$-$AND$ (outputs $0$ iff $\ge k$ bits are $0$), and thus can be seen as an interpolation between $AC^0$ and $TC^0$.

We establish a tight multi-switching lemma for $GC(k)$ circuits, which bounds the probability that several depth-2 $GC^0(k)$ circuits do not simultaneously simplify under a random restriction. We also establish a new depth reduction lemma such that coupled with our multi-switching lemma, we can show many results obtained from the multi-switching lemma for depth-$d$ size-$s$ $AC^0$ circuits lifts to depth-$d$ size-$s^{.99}$ $GC^0(.01\log s)$ circuits with no loss in parameters (other than hidden constants).

Our result has the following applications:

-Size-$2^{\Omega(n^{1/d})}$ depth-$d$ $GC^0(\Omega(n^{1/d}))$ circuits do not correlate with parity (extending a result of Håstad (SICOMP, 2014)).

-Size-$n^{\Omega(\log n)}$ $GC^0(\Omega(\log^2 n))$ circuits with $n^{.249}$ arbitrary threshold gates or $n^{.499}$ arbitrary symmetric gates exhibit exponentially small correlation against an explicit function (extending a result of Tan and Servedio (RANDOM, 2019)).

-There is a seed length $O((\log m)^{d-1}\log(m/\varepsilon)\log\log(m))$ pseudorandom generator against size-$m$ depth-$d$ $GC^0(\log m)$ circuits, matching the $AC^0$ lower bound of Håstad up to a $\log\log m$ factor (extending a result of Lyu (CCC, 2022)).

-Size-$m$ $GC^0(\log m)$ circuits have exponentially small Fourier tails (extending a result of Tal (CCC, 2017)).



Changes to previous version:

Improved presentation and layout, fixed minor inaccuracies and typos, added explicit circuit constructions matching our established lower bounds and correlation bounds


Paper:

TR23-045 | 13th April 2023 12:22

Tight Correlation Bounds for Circuits Between AC0 and TC0





TR23-045
Authors: Vinayak Kumar
Publication: 13th April 2023 14:23
Downloads: 1444
Keywords: 


Abstract:

We initiate the study of generalized $AC^0$ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight $\ge k$ (up to negations of the input bits), which we denote $GC^0(k)$. The gate set of this class includes biased LTFs like the $k$-$OR$ (outputs $1$ iff $\ge k$ bits are $1$) and $k$-$AND$ (outputs $0$ iff $\ge k$ bits are $0$), and thus can be seen as an interpolation between $AC^0$ and $TC^0$.

We establish a tight multi-switching lemma for $GC(k)$ circuits, which bounds the probability that several depth-2 $GC^0(k)$ circuits do not simultaneously simplify under a random restriction. We also establish a new depth reduction lemma such that coupled with our multi-switching lemma, we can show many results obtained from the multi-switching lemma for depth-$d$ size-$s$ $AC^0$ circuits lifts to depth-$d$ size-$s^{.99}$ $GC^0(.01\log s)$ circuits with no loss in parameters (other than hidden constants).

Our result has the following applications:

-Size-$2^{\Omega(n^{1/d})}$ depth-$d$ $GC^0(\Omega(n^{1/d}))$ circuits do not correlate with parity (extending a result of Håstad (SICOMP, 2014)).

-Size-$n^{\Omega(\log n)}$ $GC^0(\Omega(\log^2 n))$ circuits with $n^{.249}$ arbitrary threshold gates or $n^{.499}$ arbitrary symmetric gates exhibit exponentially small correlation against an explicit function (extending a result of Tan and Servedio (RANDOM, 2019)).

-There is a seed length $O((\log m)^{d-1}\log(m/\varepsilon)\log\log(m))$ pseudorandom generator against size-$m$ depth-$d$ $GC^0(\log m)$ circuits, matching the $AC^0$ lower bound of Håstad up to a $\log\log m$ factor (extending a result of Lyu (CCC, 2022)).

-Size-$m$ $GC^0(\log m)$ circuits have exponentially small Fourier tails (extending a result of Tal (CCC, 2017)).



ISSN 1433-8092 | Imprint