Depth Reduction
One benchmark in our understanding of the computation of polynomials is the work of Valiant, Skyum, Berkowitz and Rackoff. They showed that if a polynomial f of degree r has a circuit of size s, then f also has a circuit of size polynomial in r and s of depth O(log(r) log(s)). For example, any polynomial of degree n that has a polynomial size circuit, also has a polynomial size circuit of depth roughly log2(n). This result generalizes the circuit of Berkowitz to any polynomial of polynomial degree that has a polynomial size circuit (such as the determinant). The analog of this result in the Boolean setting is believed to be false.
One corollary of this result is a simulation of circuits by relatively small formulas, formulas of quasipolynomial size: if a polynomial f of degree r has a circuit of size s, then it has a formula of size sO(log r). This simulation is easier than the depth reduction of Valiant el al. and was shown earlier by Hyafil.
Read more about this topic: Arithmetic Circuit Complexity
Famous quotes containing the words depth and/or reduction:
“From the depth of the dreamydecline of the dawn through a notable
nimbus of nebulous noonshine,”
—A.C. (Algernon Charles)
“The reduction of nuclear arsenals and the removal of the threat of worldwide nuclear destruction is a measure, in my judgment, of the power and strength of a great nation.”
—Jimmy Carter (James Earl Carter, Jr.)