Reconstruction of depth three circuits with top fan-in two
Gaurav Sinha (Microsoft, Cal, USA)
5 January, 2018
Reconstruction of arithmetic circuits has been heavily studied in the past few years and has
connections to proving lower bounds and deterministic identity testing. In this talk we present
a polynomial time randomized algorithm for reconstructing depth−3 circuits with fan-in 2 at the top
addition gate and having coefficients from a characteristic zero field.
The algorithm needs only a black-box query access to the polynomial, runs in time polynomial
in input size and returns a circuit (from the above model) computing the polynomial (with high probability).
Our main techniques are based on the use of Quantitative Sylvester Gallai theorems from
recent work of Barak et.al., to find a small collection of "nice" sub-spaces onto which we restrict our input polynomial. The
heart of our work lies in applying these theorems to prove why restrictions w.r.t. the "nice" sub-spaces can be ”glued”.
We also use "Brill’s Equations" to construct a set of linear forms which are computed at the first computational (from the bottom)
layer of our arithmetic circuit.