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 recent breakthrough, Chattopadhyay, Hatami, Lee, Lovett, Tal, and Viola (ECCC'26) established exponential correlation bounds for polynomials over $\mathbf{F}_2$ and, as a consequence, obtained a major improvement in PRG constructions for low-degree polynomials over the binary field. In particular, they obtained seed length $\widetilde{O}(d^2\log^2 n)$ for fooling degree-$d$ polynomials ... more >>>
The strong Koml\'os conjecture asserts that every ordered family of Euclidean-unit vectors admits a signing whose signed prefixes have uniformly bounded \(\ell_\infty\)-norm. We disprove this conjecture by constructing explicit finite families with unbounded fixed-order prefix discrepancy. At level \(k\), our integer matrix has \(d_k=2^{2^k-1}\) rows and exactly \(s_k=2^k\) nonzero \(\pm1\) ... more >>>
We construct explicit non-malleable affine extractors for every constant entropy rate, with linear output length and exponentially small error, against any fixed number of affine tamperings without fixed points. For every fixed $00$.
Our extractors derandomize the lossless lifting of Efremenko and Itsykson (STOC 2026). For every fixed $0<\xi<1$, this ... more >>>
