Reconstruction of depth-4 multilinear circuits

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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].

Original languageEnglish (US)
Title of host publication31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
EditorsShuchi Chawla
PublisherAssociation for Computing Machinery
Pages2144-2160
Number of pages17
ISBN (Electronic)9781611975994
StatePublished - 2020
Event31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States
Duration: Jan 5 2020Jan 8 2020

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2020-January

Conference

Conference31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
Country/TerritoryUnited States
CitySalt Lake City
Period1/5/201/8/20

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Reconstruction of depth-4 multilinear circuits'. Together they form a unique fingerprint.

Cite this