ECCC-Report TR23-045https://eccc.weizmann.ac.il/report/2023/045Comments and Revisions published for TR23-045en-usThu, 25 May 2023 13:04:11 +0300
Revision 1
| Tight Correlation Bounds for Circuits Between AC0 and TC0 |
Vinayak Kumar
https://eccc.weizmann.ac.il/report/2023/045#revision1We 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)).
Thu, 25 May 2023 13:04:11 +0300https://eccc.weizmann.ac.il/report/2023/045#revision1
Paper TR23-045
| Tight Correlation Bounds for Circuits Between AC0 and TC0 |
Vinayak Kumar
https://eccc.weizmann.ac.il/report/2023/045We 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)).
Thu, 13 Apr 2023 14:23:19 +0300https://eccc.weizmann.ac.il/report/2023/045