Quantcast

On the limits of depth reduction at depth 3 over small finite fields

Research paper by SuryajithChillara1, ParthaMukhopadhyay

Indexed on: 29 Oct '17Published on: 01 Oct '17Published in: Information and Computation



Abstract

In a surprising recent result, Gupta–Kamath–Kayal–Saptharishi have proved that over Q<math class="math"><mi mathvariant="double-struck" is="true">Q</mi></math> any nO(1)<math class="math"><msup is="true"><mrow is="true"><mi is="true">n</mi></mrow><mrow is="true"><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><mn is="true">1</mn><mo stretchy="false" is="true">)</mo></mrow></msup></math>-variate and n-degree polynomial in VP can also be computed by a depth three ΣΠΣ circuit of size 2O(nlog3/2⁡n)<math class="math"><msup is="true"><mrow is="true"><mn is="true">2</mn></mrow><mrow is="true"><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><msqrt is="true"><mi is="true">n</mi></msqrt><msup is="true"><mrow is="true"><mi mathvariant="normal" is="true">log</mi></mrow><mrow is="true"><mn is="true">3</mn><mo stretchy="false" is="true">/</mo><mn is="true">2</mn></mrow></msup><mo is="true">⁡</mo><mi is="true">n</mi><mo stretchy="false" is="true">)</mo></mrow></msup></math>.2 Over fixed-size finite fields, Grigoriev and Karpinski proved that any ΣΠΣ circuit that computes the determinant (or the permanent) polynomial of a n×n<math class="math"><mi is="true">n</mi><mo is="true">×</mo><mi is="true">n</mi></math> matrix must be of size 2Ω(n)<math class="math"><msup is="true"><mrow is="true"><mn is="true">2</mn></mrow><mrow is="true"><mi mathvariant="normal" is="true">Ω</mi><mo stretchy="false" is="true">(</mo><mi is="true">n</mi><mo stretchy="false" is="true">)</mo></mrow></msup></math>. In this paper, for an explicit polynomial in VP (over fixed-size finite fields), we prove that any ΣΠΣ circuit computing it must be of size 2Ω(nlog⁡n)<math class="math"><msup is="true"><mrow is="true"><mn is="true">2</mn></mrow><mrow is="true"><mi mathvariant="normal" is="true">Ω</mi><mo stretchy="false" is="true">(</mo><mi is="true">n</mi><mi mathvariant="normal" is="true">log</mi><mo is="true">⁡</mo><mi is="true">n</mi><mo stretchy="false" is="true">)</mo></mrow></msup></math>. The explicit polynomial that we consider is the iterated matrix multiplication polynomial of n generic matrices of size n×n<math class="math"><mi is="true">n</mi><mo is="true">×</mo><mi is="true">n</mi></math>. The importance of this result is that over fixed-size fields there is no depth reduction technique that can be used to compute all the nO(1)<math class="math"><msup is="true"><mrow is="true"><mi is="true">n</mi></mrow><mrow is="true"><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><mn is="true">1</mn><mo stretchy="false" is="true">)</mo></mrow></msup></math>-variate and n-degree polynomials in VP by depth 3 circuits of size 2o(nlog⁡n)<math class="math"><msup is="true"><mrow is="true"><mn is="true">2</mn></mrow><mrow is="true"><mi is="true">o</mi><mo stretchy="false" is="true">(</mo><mi is="true">n</mi><mi mathvariant="normal" is="true">log</mi><mo is="true">⁡</mo><mi is="true">n</mi><mo stretchy="false" is="true">)</mo></mrow></msup></math>. The result of Grigoriev and Karpinski can only rule out such a possibility for ΣΠΣ circuits of size 2o(n)<math class="math"><msup is="true"><mrow is="true"><mn is="true">2</mn></mrow><mrow is="true"><mi is="true">o</mi><mo stretchy="false" is="true">(</mo><mi is="true">n</mi><mo stretchy="false" is="true">)</mo></mrow></msup></math>.