Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR15-150 | 13th September 2015
Gaurav Sinha

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

Revisions: 3

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

ISSN 1433-8092 | Imprint