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 exhibit a total Boolean function on n input bits whose bounded-error quantum simultaneous-message (and hence one-way) communication complexity is in O(?n), whereas its randomised one-way (and hence simultaneous-message) communication complexity is in ?(n).
The same function admits a classical simultaneous-message protocol of cost O(?n) when the players share O(?n) ...
more >>>
The no-cloning theorem imposes a fundamental limit on quantum error correction. It implies that no code is resilient to a half fraction of adversarial erasures: otherwise, we can clone by decoding from two disjoint halves of the encoding. This argument works because the encoding does not depend on the receiver, ... more >>>
In the information dissemination problem, $n$ parties each hold a unique piece of information and wish to learn all the information. They communicate over an adversarial broadcast channel, where an adversary may corrupt a fraction of the received transmissions. What is the largest fraction of errors to which an information ... more >>>