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.
Proving super-linear lower bounds on the size of circuits computing explicit linear functions $A:{\mathbb {F}}^n \to {\mathbb {F}}^n$ is a fundamental long-standing open problem in circuit complexity. We focus on the case where ${\mathbb {F}}$ is a finite field. The circuit can be either a Boolean circuit or an arithmetic ... more >>>
Res($\oplus$) is the simplest fragment of $\text{AC}^0[2]\text{-Frege}$ for which no super-polynomial lower bounds on the size of proofs are known. Bhattacharya and Chattopadhyay [BC25] recently proved lower bounds of the form $\exp(\tilde\Omega(N^{\varepsilon}))$ on the size of Res($\oplus$) proofs whose depth is upper bounded by $O(N^{2 - \varepsilon})$, where $N$ is ... more >>>
We prove that relative to a random oracle answering $O(\log n)$-bit queries, there exists a function computable in $O(n)$ time by a random-access machine (RAM) but requiring $n^2/polylog(n)$ time by any multitape Turing machine. This provides strong evidence that simulating RAMs on multitape Turing machines inherently incurs a nearly quadratic ... more >>>
