Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DEPTH 3 ARITHMETIC CIRCUIT:
Reports tagged with depth 3 arithmetic circuit:
TR20-125 | 17th August 2020
Gaurav Sinha

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

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




ISSN 1433-8092 | Imprint