Loading jsMath...
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: 455
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: 2057
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