All reports by Author Gaurav Sinha:

__
TR20-125
| 17th August 2020
__

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

Revisions: 2

__
TR15-150
| 13th September 2015
__

Gaurav Sinha#### Reconstruction of $\Sigma\Pi\Sigma(2)$ Circuits over Reals

Revisions: 3

Gaurav Sinha

In this paper 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 top(output) gate is an addition gate with in-degree $2$. Such circuits naturally compute polynomials of the form $G\times(T_1 + T_2)$, ... more >>>

Gaurav Sinha

Reconstruction of arithmertic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing $\Sigma\Pi\Sigma(2)$ circuits over $\R$, i.e. depth$-3$ circuits with fan-in $2$ at the top addition ... more >>>