# Efficient reconstruction of depth three circuits with top fan-in two

arXiv: https://arxiv.org/abs/2103.07445 · HTML: https://mlsanity.com/paper/2103.07445/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 50 references that are in the map.
- First posted on arXiv 12 Mar 2021.

## Builds on (most cited first, 2 of 2)

- [Learning sums of powers of low-degree polynomials in the non-degenerate case](https://mlsanity.com/paper/2004.06898/) (2020)
- [Reconstruction of depth-3, top fan-in two circuits over characteristic zero fields](https://mlsanity.com/paper/1512.01256/) (2015)

## Built on by (most cited first, 1 of 1)

- [Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits](https://mlsanity.com/paper/2105.01751/) (2021)

## Abstract (arXiv)

We develop efficient randomized algorithms to solve the black-box reconstruction problem for polynomials over finite fields, computable by depth three arithmetic circuits with alternating addition/multiplication gates, such that output gate is an addition gate with in-degree two. These circuits compute polynomials of form G×(T1 + T2), where G,T1,T2 are product of affine forms, and polynomials T1,T2 have no common factors. Rank of such a circuit is defined as dimension of vector space spanned by all affine factors of T1 and T2. For any polynomial f computable by such a circuit, rank(f) is defined to be the minimum rank of any such circuit computing it. Our work develops randomized reconstruction algorithms which take as input black-box access to a polynomial f (over finite field mathbbF), computable by such a circuit. Here are the results. 1 [Low rank]: When 5≤ rank(f) = O(log3 d), it runs in time (ndlog3dlog |mathbbF|)O(1), and, with high probability, outputs a depth three circuit computing f, with top addition gate having in-degree ≤ drank(f). 2 [High rank]: When rank(f) = Omega(log3 d), it runs in time (ndlog |mathbbF|)O(1), and, with high probability, outputs a depth three circuit computing f, with top addition gate having in-degree two. Ours is the first blackbox reconstruction algorithm for this circuit class, that runs in time polynomial in log |mathbbF|. This problem has been mentioned as an open problem in [GKL12] (STOC 2012)