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:
“Love and work are viewed and experienced as totally separate activities motivated by separate needs. Yet, when we think about it, our common sense tells us that our most inspired, creative acts are deeply tied to our need to love and that, when we lack love, we find it difficult to work creatively; that work without love is dead, mechanical, sheer competence without vitality, that love without work grows boring, monotonous, lacks depth and passion.”
—Marta Zahaykevich, Ucranian born-U.S. psychitrist. “Critical Perspectives on Adult Women’s Development,” (1980)
“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.)