Reconstruction of Depth-4 Multilinear Circuits
Open Access
- 28 March 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
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 \in \mathbb {F}[x_{1},x_{2},\ldots,x_{n} ] \) computable by a multilinear ΣΠΣΠ ( k ) circuit of size s , the algorithm runs in time quasi-poly( \(n,s,|\mathbb {F}|) \) and outputs a multilinear ΣΠΣΠ ( k ) circuit of size quasi-poly( n , s ) that computes f . Our result solves an open problem posed in [GKL12] (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear ΣΠΣΠ ( k ) circuits were known only for the case of k = 2 [GKL12,Vol17].
Keywords
This publication has 26 references indexed in Scilit:
- Black-Box Identity Testing of Depth-4 Multilinear CircuitsCombinatorica, 2017
- Read-once polynomial identity testingcomputational complexity, 2015
- Random arithmetic formulas can be reconstructed efficientlycomputational complexity, 2014
- Improved Bounds for Reduction to Depth 4 and Depth 32013
- Efficient learning algorithms yield circuit lower boundsJournal of Computer and System Sciences, 2009
- Polynomial Identity Testing for Depth 3 Circuitscomputational complexity, 2007
- Pseudorandom Generators without the XOR LemmaJournal of Computer and System Sciences, 2001
- On Interpolating Arithmetic Read-Once Formulas with ExponentiationJournal of Computer and System Sciences, 1998
- Tensor rank is NP-completeJournal of Algorithms, 1990
- A probabilistic remark on algebraic program testingInformation Processing Letters, 1978