|
|
|
|
LOn the Power of Small-Depth Computation
Foundations and Trends® in
Theoretical Computer Science
Volume 5 Issue 1
On the Power of Small-Depth Computation
Emanuele Viola
Northeastern University viola@ccs.neu.edu
SUGGESTED CITATION:
Emanuele Viola (2009)
"On the Power of Small-Depth Computation",
Foundations and Trends® in Theoretical Computer Science: Vol. 5: No 1, pp 1-72.
http://dx.doi.org/10.1561/0400000033
Abstract
In this work we discuss selected topics on small-depth computation, presenting a few unpublished proofs along the way. The four sections contain:
(1) A unified treatment of the challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over {0, 1}.
(2) 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.
(3) 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.
(4) Applebaum, Ishai, and Kushilevitz's cryptography in bounded depth.
|
|
|
|
|
|
|
|
|