On the Power of Small-Depth Computation
Foundations and Trends® in Theoretical Computer Science · 2009
DOI: 10.1561/0400000033 ↗Kurz gefasst
Fachartikel in der Zeitschrift Foundations and Trends® in Theoretical Computer Science, 2009. Verfasst von Emanuele Viola. Die Arbeit wurde bisher 18-mal zitiert (Crossref) und nennt 81 Literaturangaben.
Abstract (Originalsprache)
In this monograph we discuss selected topics on small-depth computation, presenting a few unpublished proofs along the way. The four sections contain: A unified treatment of the challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over {0,1}.An unpublished proof that small bounded-depth circuits (AC0) have exponentially small correlation with the parity function. The proof is due to Klivans and Vadhan; it builds upon and simplifies previous ones.Valiant’s simulation of log-depth linear-size circuits of fan-in 2 by sub-exponential size circuits of depth 3 and unbounded fan-in. To our knowledge, a proof of this result has never appeared in full.Applebaum, Ishai, and Kushilevitz’s cryptography in bounded depth.
Zitieren
APA
Viola, E. (2009). On the Power of Small-Depth Computation. Foundations and Trends® in Theoretical Computer Science. https://doi.org/10.1561/0400000033
Vancouver
Viola E. On the Power of Small-Depth Computation. Foundations and Trends® in Theoretical Computer Science. 2009. doi:10.1561/0400000033
BibTeX
@article{Viola2009,
author = {Viola, Emanuele},
title = {On the Power of Small-Depth Computation},
journal = {Foundations and Trends® in Theoretical Computer Science},
year = {2009},
doi = {10.1561/0400000033}
}
EUVIMED