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:
“To whatsoever upright mind, to whatsoever beating heart I speak, to you it is committed to educate men. By simple living, by an illimitable soul, you inspire, you correct, you instruct, you raise, you embellish all. By your own act you teach the beholder how to do the practicable. According to the depth from which you draw your life, such is the depth not only of your strenuous effort, but of your manners and presence.”
—Ralph Waldo Emerson (1803–1882)
“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.)