Arithmetic circuits: The chasm at depth four gets wider

作者：Koiran Pascal^*

来源：Theoretical Computer Science, 2012, 448: 56-65.

DOI：10.1016/j.tcs.2012.03.041

• Arithmetic circuits
• Depth reduction
• Lower bounds
• Identity testing

In their paper on the "chasm at depth four", Agrawal and Vinay have shown that polynomials in m variables of degree O(m) which admit arithmetic circuits of size 2(0(m)) also admit arithmetic circuits of depth four and size 2(0(m)). This theorem shows that for problems such as arithmetic circuit lower bounds or black-box derandomization of identity testing, the case of depth four circuits is in a certain sense the general case.
In this paper we show that smaller depth four circuits can be obtained if we start from polynomial size arithmetic circuits. For instance, we show that if the permanent of n x n matrices has circuits of size polynomial in n, then it also has depth 4 circuits of size n(O(root n log n)). If the original circuit uses only integer constants of polynomial size, then the same is true for the resulting depth four circuit. These results have potential applications to lower bounds and deterministic identity testing, in particular for sums of products of sparse univariate polynomials. We also use our techniques to reprove two results on:
- the existence of nontrivial boolean circuits of constant depth for languages in LOGCFL;
- reduction to polylogarithmic depth for arithmetic circuits of polynomial size and polynomially bounded degree.

• 出版日期2012-8-24
• 单位INRIA