Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NARMADA VARADARAJAN:
All reports by Author Narmada Varadarajan:

TR25-222 | 29th December 2025
Shubhangi Saraf, Devansh Shringi, Narmada Varadarajan

Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-in

In this paper, we give the first subexponential (in fact, quasi-polynomial time) reconstruction algorithm for depth-3 circuits of any constant top fan-in ($\Sigma\Pi\Sigma(k)$ circuits) over $\mathbb R$, $\mathbb C$, or any large characteristic finite field $\mathbb F$. More explicitly, we show that for any constant $k$, given black-box access to ... more >>>




ISSN 1433-8092 | Imprint