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

In an earlier note (arXiv:2606.11090) I showed that the border determinantal complexity of the power sum x_1^d + ... + x_N^d is ?(Nd). The proof counted the simple solutions of an explicit polynomial system and compared that number with what a small determinant can produce. This left two questions. Does ... more >>>