We study factoring algorithms for general sparse polynomials and sparse polynomials of bounded individual degree and prove the following results.
1. We give a deterministic polynomial-time algorithm which takes as input an $n$-variate $s$-sparse polynomial $f$ of bounded individual degree $d$ and outputs a list of circuits which contains ... more >>>

We study depth-$5$ algebraic circuits over small finite fields with restricted fan-in of the top product gates. We show that there exists an explicit degree-$d$ polynomial $P(\mathbf{x})$ such that any $\Sigma \Pi^{[\mathrm{poly(d)}]} \Sigma \Pi \Sigma$ circuit, computing $P(\mathbf{x})$, over a small finite field, requires size $2^{\Omega(\sqrt{d})}$. Our work builds upon ... more >>>

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{\Omega(\log k)}$ queries.

The ... more >>>