Foundations and Trends® in Theoretical Computer Science > Vol 5 > Issue 1

On the Power of Small-Depth Computation

By Emanuele Viola, Northeastern University, USA, 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

Publication Date: 24 Nov 2009
© 2009 E. Viola
 
Subjects
Computational complexity
 

Free Preview:

Download extract

Share

Download article
In this article:
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 

Abstract

In this monograph we discuss selected topics on small-depth computation, presenting a few unpublished proofs along the way. The four sections contain:

  1. (1) A unified treatment of the challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over {0,1}.
  2. (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. (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. (4) Applebaum, Ishai, and Kushilevitz's cryptography in bounded depth.

DOI:10.1561/0400000033
ISBN: 978-1-60198-300-8
88 pp. $59.00
Buy book (pb)
 
ISBN: 978-1-60198-301-5
88 pp. $100.00
Buy E-book (.pdf)
Table of contents:
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

On the Power of Small-Depth Computation

The NP-completeness of SAT is a celebrated example of the power of bounded-depth computation: the core of the argument is a depth reduction establishing that any small non-deterministic circuit – an arbitrary NP computation on an arbitrary input – can be simulated by a small non-deterministic circuit of depth 2 with unbounded fan-in – a SAT instance. Many other examples permeate theoretical computer science. On the Power of Small-Depth Computation discusses a selected subset of them, and includes a few unpublished proofs. On the Power of Small-Depth Computation starts with a unified treatment of the challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over {0, 1}. It goes on to describe an unpublished proof that small bounded-depth circuits (AC0) have exponentially small correlation with the parity function. The proof is due to Adam Klivans and Salil Vadhan; it builds upon and simplifies previous ones. Thereafter it looks at a depth-reduction result by Leslie Valiant, the proof of which has not before appeared in full. It concludes by presenting the result by Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz that shows that, under standard complexity theoretic assumptions, many cryptographic primitives can be implemented in very restricted computational models. On the Power of Small-Depth Computation is an ideal primer for anyone with an interest in computational complexity, random structures and algorithms and theoretical computer science generally.

 
TCS-033