In the reconstruction problem for a multivariate polynomial $f$, we have blackbox access to $f$ and the goal is to efficiently reconstruct a representation of $f$ in a suitable model of computation. We give a polynomial time randomized algorithm for reconstructing *random* arithmetic formulas. Our algorithm succeeds with high probability when given blackbox access to the polynomial computed by a random formula according to a natural distribution. Previous results on this problem considered models such as depth-3 circuits with various restrictions or read-once formulas, as well as multilinear depth-4 circuits with top fan-in 2, and random multilinear formulas (which Satya Lokam just talked about here).

Our result then is the most natural model of arithmetic computation (e.g. without various constraints, notably without multilinear constraint) for which a reconstruction algorithm is presently known, albeit efficient in a distributional sense rather than in the worst case. The main technical work involved in devising the above algorithm is understanding and characterizing the high-dimensional components of the singular locus of an arbitrary linear combination of (a few) random formulas.

Joint work with Ankit Gupta and Neeraj Kayal.