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 recent manuscript of OpenAI proves that the exponent of matrix multiplication satisfies $\omega\le9/4$. We give an elementary, self-contained proof of this bound. We follow the ideas of the original manuscript, but implement them differently to obtain explicit algorithms. Specifically, for every $\varepsilon>0$, we give a matrix multiplication algorithm with ... more >>>
One of the central questions in space complexity is whether nondeterministic logspace computations (NL) can be simulated in unambiguous logspace (UL). A stronger notion, reach unambiguity (RUL $\subseteq$ UL $\cap$ coUL), requires every configuration reachable from the start to have exactly one computation path (Buntrock et.al. 91). While directed graph ... more >>>
In this work, we design knowledge compilation languages for quantified Boolean formulas (QBFs), with a particular focus on model counting. We introduce various languages in increasing order of their power of representation, starting from a simple tree-based structure, and extending it to DAGs for a more efficient representation. We study ... more >>>
