INTERPOLATION OF DEPTH-3 ARITHMETIC CIRCUITS WITH TWO MULTIPLICATION GATES

摘要

In this paper we consider the problem of constructing a small arithmetic circuit for a polynomial for which we have oracle access. Our focus is on n-variate polynomials, over a finite field F, that have depth-3 arithmetic circuits (with an addition gate at the top) with two multiplication gates of degree at most d. We obtain the following results: 1. Multilinear case. When the circuit is multilinear (multiplication gates compute multilinear polynomials) we give an algorithm that outputs, with probability 1 - o(1), all the depth-3 circuits with two multiplication gates computing the polynomial. The running time of the algorithm is poly(n, |F|). 2. General case. When the circuit is not multilinear we give a quasi-polynomial (in n, d, |F|) time algorithm that outputs, with probability 1-o(1), a succinct representation of the polynomial. In particular, if the depth-3 circuit for the polynomial is not of small depth-3 rank (namely, after removing the g.c.d. (greatest common divisor) of the two multiplication gates, the remaining linear functions span a not too small linear space), then we output the depth-3 circuit itself. In the case that the rank is small we output a depth-3 circuit with a quasi-polynomial number of multiplication gates. Prior to our work there have been several interpolation algorithms for restricted models. However, all the techniques used there completely fail when dealing with depth-3 circuits with even just two multiplication gates.Our proof technique is new and relies on the factorization algorithm for multivariate black-box polynomials, on lower bounds on the length of linear locally decodable codes with two queries, and on a theorem regarding the structure of identically zero depth-3 circuits with four multiplication gates.