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.
In a $k$-XOR game $\Psi$ over $\mathbb{F}_p$, a verifier samples challenges $(x_1,\ldots,x_k)\sim\mu$ where $\mu$ is a distribution over $\Sigma_1\times\ldots\times \Sigma_k$, sends $x_i$ to player $i$ and receives an answer $f_i(x_i)\in\mathbb{F}_p$, and accepts if and only if $f_1(x_1)+\ldots+f_k(x_k)=t(x_1,\ldots,x_k)$, where $t\colon \Sigma_1\times\ldots\times \Sigma_k\to\mathbb{F}_p$ is a fixed map. We show that if $\Psi$ ... more >>>
The Poisson approximation theorem states that when $m$ balls are tossed uniformly and randomly into $n$ bins, the distribution of the bin loads can sometimes be approximated by $n$ independent Poisson random variables of mean $m/n$. We show that when the balls are tossed via a random $\mathbb{F}_2$-linear map, ... more >>>
Sparsity is a basis-dependent notion: a polynomial with many monomials may become sparse after an invertible affine change of variables. We study polynomial identity testing (PIT) and lower bounds for sparse polynomials under arbitrary invertible affine changes of coordinates, that is, for affine orbits of sparse polynomials. For PIT, the ... more >>>
