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.
Kane and Williams proved average-case wire lower bounds at the $n^{5/2}/\mathrm{polylog}, n$ scale for an explicit function against depth-two linear-threshold circuits. We prove an almost-everywhere near-cubic wire lower bound for a language in $\mathrm{E}^{\mathrm{NP}}$. For every fixed $c>0$, there is one language $F_c$ and positive constants $b_{S,c}$ and $b_{T,c}$ such ... more >>>
Grochow and Pitassi (2018) introduced the algebraic proof system, the Ideal Proof System (IPS), which connects algebraic circuit complexity to propositional proof complexity. They showed that propositional proof systems such as Extended Frege (Frege) are equivalent to circuit IPS (formula IPS) if the correctness of PIT for circuits (formulas) can ... more >>>
In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model. We prove the first circuit lower bounds for Group Isomorphism: namely, we show that every family of depth-$2$ Boolean circuits deciding Group Isomorphism requires quasipolynomial-size. We complement this with upper bounds of ... more >>>
