Submissions claiming to resolve a grand challenge, such as the P vs. NP problem, may be rejected without further consideration.
Submissions containing an essential part that seems to be generated by AI tools and/or are written in a way that humans will find hard to understand, may be rejected regardless of their merits. ECCC is intended for communication among humans.
For more details see the Call for Papers.In the last few days, a Denial of Service attack was launched on universities in Israel, leading the administrators of the Israel Academic network to block access to it from the global internet. Consequently, websites such as ECCC have been accessible only from within the Israeli and European academic networks.
It seems that this blocking was just removed, and we hope it will not be put back in the future.
Needless to say, deciding on such blocking is not in our control, but we do apologize for this disruption of service.
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 >>>
