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 continue to investigate input-oblivious computations and build a map of known and new complexity classes. In particular,
* We prove a new upper bound for $OL_2^P$ defined by Hirsch and Volkovich (STACS, 2026), which is a natural input-oblivious version of the $L_2^P$ class of Korten and Pitassi (FOCS, 2024): ...
more >>>
The idea that learning is closely tied to compression has long served as both a powerful principle and,
at times, an informal analogy across machine learning and learning theory. Here we focus on settings in
which that intuition can be made mathematically precise, surveying formal connections among learning
algorithms, data ...
more >>>
A constant-depth circuit consists of AND and OR gates of unbounded fan-in, arranged in a constant number of layers, that read the input literals; for example, a depth-three circuit is an OR of CNFs or an AND of DNFs. The classical lower bound of Håstad (1989) states that every depth-$d$ ... more >>>
