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.
A pruning procedure maps a Boolean circuit to a circuit on the same variables that accepts only satisfying assignments of the original.
Valiant and Vazirani give a pruning procedure that leaves exactly one satisfying assignment of every satisfiable circuit with probability $\Omega(1/n)$, where $n$ is the number of variables. Dell, ...
more >>>
Border complexity captures polynomials that can be approximated arbitrarily well by small algebraic circuits, and debordering asks how efficiently such an approximation can be converted into an exact computation. Debordering lies at the heart of the gap between Valiant's determinant versus permanent conjecture and its strengthening by Mulmuley and Sohoni ... more >>>
We prove an $\Omega((\log n/\log\log n)^2)$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in $n$-node directed acyclic graphs under edge insertions. This improves the $\widetilde{\Omega}(\log^{3/2} n)$ lower bound of Larsen and Yu [SICOMP 2025], and matches the ... more >>>
