License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.18
URN: urn:nbn:de:0030-drops-182885
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18288/
Kumar, Vinayak M.
Tight Correlation Bounds for Circuits Between AC0 and TC0
Abstract
We initiate the study of generalized AC⁰ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight ≥ k (up to negations of the input bits), which we denote GC⁰(k). The gate set of this class includes biased LTFs like the k-OR (outputs 1 iff ≥ k bits are 1) and k-AND (outputs 0 iff ≥ k bits are 0), and thus can be seen as an interpolation between AC⁰ and TC⁰.
We establish a tight multi-switching lemma for GC⁰(k) circuits, which bounds the probability that several depth-2 GC⁰(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⁰ circuits lifts to depth-d size-s^{.99} GC⁰(.01 log s) circuits with no loss in parameters (other than hidden constants).
Our result has the following applications:
- Size-2^Ω(n^{1/d}) depth-d GC⁰(Ω(n^{1/d})) circuits do not correlate with parity (extending a result of Håstad (SICOMP, 2014)).
- Size-n^Ω(log n) GC⁰(Ω(log² 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/ε)log log(m)) pseudorandom generator against size-m depth-d GC⁰(log m) circuits, matching the AC⁰ lower bound of Håstad up to a log log m factor (extending a result of Lyu (CCC, 2022)).
- Size-m GC⁰(log m) circuits have exponentially small Fourier tails (extending a result of Tal (CCC, 2017)).
BibTeX - Entry
@InProceedings{kumar:LIPIcs.CCC.2023.18,
author = {Kumar, Vinayak M.},
title = {{Tight Correlation Bounds for Circuits Between AC0 and TC0}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {18:1--18:40},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-282-2},
ISSN = {1868-8969},
year = {2023},
volume = {264},
editor = {Ta-Shma, Amnon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18288},
URN = {urn:nbn:de:0030-drops-182885},
doi = {10.4230/LIPIcs.CCC.2023.18},
annote = {Keywords: AC⁰, TC⁰, Switching Lemma, Lower Bounds, Correlation Bounds, Circuit Complexity}
}
|
Keywords: |
|
AC⁰, TC⁰, Switching Lemma, Lower Bounds, Correlation Bounds, Circuit Complexity |
|
Collection: |
|
38th Computational Complexity Conference (CCC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
10.07.2023 |
