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 study the subclass of $\mathrm{prAM}$ problems such that derandomizing the corresponding Arthur--Merlin verifier (i.e. to an $\mathrm{NP}$ verifier) reduces to the Range Avoidance problem ($\mathrm{Avoid}$), the total search problem of finding a string outside the range of an expanding circuit.
We prove a new ...
more >>>
Determining the communication complexity of graph connectivity has been one of the longest standing open problems in communication complexity since the seminal work of Babai, Frankl, and Simon [FOCS'86]. A simple protocol transmits a spanning forest using $O(N\log N)$ communication on $N$-vertex graphs. While this was shown optimal for deterministic ... more >>>
We prove a linear query complexity lower bound for two-sided testing of graph isomorphism in the bounded-degree model.
Specifically, there are constants $d$ and $\varepsilon_0$ such that, for every sufficiently large $n$,
there exists an $n$-vertex graph $H_n$ of maximum degree at most $d$ such that testing isomorphism ...
more >>>
