| Series |
Foundations and trends in theoretical computer science, 1551-3068 ; v. 5, issue 1, p. 1-72
Foundations and trends in theoretical computer science ; v. 5, issue 1, p. 1-72. UNAUTHORIZED
|
| Contents |
Abstract -- 1. Introduction -- 2. Polynomials over {0,1} -- 3. The correlation of parity with small-depth circuits -- 4. Logarithmic depth vs. depth 3 -- 5. Cryptography in bounded depth -- References. |
| Summary |
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. |
| Bibliography note | Includes bibliographical references (p. 69-74). |
| ISBN | 9781601983008 |
| ISBN | 160198300X |
