DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2023.18

Tight Correlation Bounds for Circuits Between AC0 and TC0

Authors: Vinayak M. Kumar

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

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)).

Cite as

Vinayak M. Kumar. Tight Correlation Bounds for Circuits Between AC0 and TC0. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 18:1-18:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.CCC.2023.18},
  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}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2021.48

Pseudobinomiality of the Sticky Random Walk

Authors: Venkatesan Guruswami and Vinayak M. Kumar

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract

Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number M of marked vertices visited in a long n-step random walk strongly concentrates around the expected n/2 value. Surprisingly, it was recently shown that the parity of M also has exponentially small bias. Is there a common unification of these results? What other statistics about M resemble the binomial distribution (the Hamming weight of a random n-bit string)? To gain insight into such questions, we analyze a simpler model called the sticky random walk. This model is a natural stepping stone towards understanding expander random walks, and we also show that it is a necessary step. The sticky random walk starts with a random bit and then each subsequent bit independently equals the previous bit with probability (1+λ)/2. Here λ is the proxy for the expander’s (second largest) eigenvalue. Using Krawtchouk expansion of functions, we derive several probabilistic results about the sticky random walk. We show an asymptotically tight Θ(λ) bound on the total variation distance between the (Hamming weight of the) sticky walk and the binomial distribution. We prove that the correlation between the majority and parity bit of the sticky walk is bounded by O(n^{-1/4}). This lends hope to unifying Chernoff bounds and parity concentration, as well as establishing other interesting statistical properties, of expander random walks.

Cite as

Venkatesan Guruswami and Vinayak M. Kumar. Pseudobinomiality of the Sticky Random Walk. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 48:1-48:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.ITCS.2021.48,
  author =	{Guruswami, Venkatesan and Kumar, Vinayak M.},
  title =	{{Pseudobinomiality of the Sticky Random Walk}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{48:1--48:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.48},
  URN =		{urn:nbn:de:0030-drops-135870},
  doi =		{10.4230/LIPIcs.ITCS.2021.48},
  annote =	{Keywords: Expander Graphs, Fourier analysis, Markov Chains, Pseudorandomness, Random Walks}
}

Search Results

Documents authored by Kumar, Vinayak M.

Tight Correlation Bounds for Circuits Between AC0 and TC0

Abstract

Cite as

Pseudobinomiality of the Sticky Random Walk

Abstract

Cite as

Thanks for your feedback!

Could not send message