TY - GEN

T1 - Reconstruction of depth-4 multilinear circuits

AU - Bhargava, Vishwas

AU - Saraf, Shubhangi

AU - Volkovich, Ilya

N1 - Funding Information:
Research supported in part by NSF grant CCF-1350572. Research supported in part by NSF grants CCF-1350572, CCF-1540634 and CCF-1412958, BSF grant 2014359, a Sloan research fellowship and the Simons Collaboration on Algorithms and Geometry. Part of the research was done when the first author was interning at Microsoft Research, India. The third author would like to thank Alex Samorodnitsky and Rafael Oliveira for many useful conversations. The authors would also like to thank the anonymous referees for their detailed comments and suggestions.

PY - 2020

Y1 - 2020

N2 - We present a deterministic algorithm for reconstructing multilinear ΣΠΣΠ(k) circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. For any fixed k, given black-box access to a polynomial f ∈ F[x1, x2, . . ., xn] computable by a multilinear ΣΠΣΠ(k) circuit of size s, the algorithm runs in time quasipoly(n, s, |F|) and outputs a multilinear ΣΠΣΠ(k) circuit of size quasi-poly(n, s) that computes f. Our result solves an open problem posed in [15] (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear ΣΠΣΠ(k) circuits were known only for the case of k = 2 [15, 52].

AB - We present a deterministic algorithm for reconstructing multilinear ΣΠΣΠ(k) circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. For any fixed k, given black-box access to a polynomial f ∈ F[x1, x2, . . ., xn] computable by a multilinear ΣΠΣΠ(k) circuit of size s, the algorithm runs in time quasipoly(n, s, |F|) and outputs a multilinear ΣΠΣΠ(k) circuit of size quasi-poly(n, s) that computes f. Our result solves an open problem posed in [15] (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear ΣΠΣΠ(k) circuits were known only for the case of k = 2 [15, 52].

UR - http://www.scopus.com/inward/record.url?scp=85084055746&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85084055746&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85084055746

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2144

EP - 2160

BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

A2 - Chawla, Shuchi

PB - Association for Computing Machinery

T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

Y2 - 5 January 2020 through 8 January 2020

ER -