Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-In

In this paper, we give the first subexponential (in fact, quasi-polynomial time) reconstruction algorithm for depth-3 circuits of any constant top fan-in (ΣΠΣ(k) circuits) over R, C, or any large characteristic finite field F. More explicitly, we show that for any constant k, given blackbox access to an n-variate polynomial f computed by a ΣΠΣ(k) circuit of size s, there is a randomized algorithm that runs in time quasi-poly(n, s) and outputs a generalized ΣΠΣ(k) circuit computing f . The size s includes the bit complexity of coefficients appearing in the circuit: this is the max bit complexity if the field is R or C, and log |F| if the field is finite.

Depth-3 circuits of constant fan-in (ΣΠΣ(k) circuits) and closely related models have been very well studied in the context of polynomial identity testing (PIT). In this paper, we build upon the structural results for identically zero ΣΠΣ(k) circuits that were studied in the context of PIT. Using connections to discrete geometry, we prove new structural properties of vanishing spaces of polynomials computed by such circuits.

Prior to our work, the only subexponential reconstruction algorithm for ΣΠΣ(k) circuits is by [Karnin-Shpilka, CCC 2009]. However, the run time is quasipolynomial in |F|, and hence this is only efficient over small finite fields. Over general (potentially exponentially large size) finite fields, efficient reconstruction algorithms were only known for k = 2 ([Sinha, ITCS 2022]); and over R and C, they were only known for k = 2 ([Sinha, CCC 2016]) and k = 3 ([Saraf-Shringi, CCC 2025]).