On the power of small-depth computation / Emanuele Viola.
| Author/creator | Viola, Emanuele |
| Format | Book |
| Publication Info | Hanover, Mass. : Now Publishers, ©2009. |
| Description | ix, 74 pages : illustrations ; 24 cm. |
| Subjects |
| 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 |
Availability
| Library | Location | Call Number | Status | Item Actions |
|---|---|---|---|---|
| Joyner | General Stacks | QA76.9.M35 V566 2009 | ✔ Available | Place Hold |