The question of optimal derandomization, introduced by Doron et. al (JACM 2022), garnered significant recent attention. Works in recent years showed conditional superfast derandomization algorithms, as well as conditional impossibility results, and barriers for obtaining superfast derandomization using certain black-box techniques.

Of particular interest is the extreme high-end, which ... more >>>

The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash ... more >>>

In this paper, we give the first subexponential (and in fact quasi-polynomial time) reconstruction algorithm for depth 3 circuits of top fan-in 3 ($\Sigma\Pi\Sigma(3)$ circuits) over the fields $\mathbb{R}$ and $\mathbb C$. Concretely, we show that given blackbox access to an $n$-variate polynomial $f$ computed by a $\Sigma\Pi\Sigma(3)$ circuit of ... more >>>