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:
“Man tells his aspiration in his God; but in his demon he shows his depth of experience; and casts light into the cavern through which he worked his cause up to the cheerful day.”
—Margaret Fuller (1810–1850)
“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.)