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 one-way quantum communication lower bounds for search problems.Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of ... more >>>
We explore the torus polynomial approximation based approach towards a long-standing question: whether AND can be computed by $CC^0$ circuits - the class of constant-depth polynomial size circuits containing $MOD_m$ gates for some natural number $m$.
Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach ...
more >>>
We prove an $\tilde{\Omega}(n^2)$ lower bound for read-once parity branching programs computing an explicit boolean function on $n$ variables. The previous best lower bound was $\tilde{\Omega}(n^{1.5})$. Our lower bound is proved by reducing the problem to a lower bound in algebraic circuit complexity.
more >>>
