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

We give a meta-complexity characterization of EFI pairs, which are considered the ''minimal'' primitive in quantum cryptography (and are equivalent to quantum commitments). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the ... more >>>

A recent result of Ghentiyala, Li, and Stephens-Davidowitz (ECCC TR 25-210) shows that any language reducible to the Range Avoidance Problem (Avoid) via deterministic or randomized Turing reductions is contained in AM $\cap$ coAM. In this note, we present a different potential avenue for obtaining the same result via the ... more >>>