EUVIMEDTutustu EUVIMEDiin
Crossref

On the Power of Small-Depth Computation

Emanuele Viola

Foundations and Trends® in Theoretical Computer Science · 2009

DOI: 10.1561/0400000033 ↗

At a glance

Journal article in Foundations and Trends® in Theoretical Computer Science, 2009. Written by Emanuele Viola. Cited 18 times so far (Crossref); 81 references.

TiivistelmäBibliografiset tiedotCiteRelated studies

Abstract (original language)

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.

Cite

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}
}
Start for free →