Let $\F$ be a finite field. Given $N$ distinct points $\bm{\alpha}_1,\ldots,\bm{\alpha}_N \in \F^m$ and associated values $\beta_1,\ldots,\beta_N \in \F$, we study the problem of computing an $m$-variate polynomial $f(\vy) \in \F[\vy]$ of individual degree less than $d$, with $d^m \ge N$, that satisfies $f(\bm{\alpha}_i)=\beta_i$ for all $i\in[N]$, whenever such an ... more >>>

We initiate the study of the meta-mathematics of algebraic circuit lower bounds, aiming both to gain insight into the methods sufficient and necessary to prove algebraic circuit lower bounds, and to contribute to the study of bounded arithmetic as a logical foundation for complexity lower bounds. We demonstrate that while ... more >>>

We study the fundamental problem of PAC learning positive linear combinations of $k$
arbitrary ReLU activations on $\mathbb{R}^d$ with respect to the Gaussian distribution, in $L_2$
loss. We give the first fully-polynomial time algorithm for this learning task.
Specifically, our algorithm draws $\mathrm{poly}(d, k, 1/\epsilon)$ samples,
more >>>