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.
In this work, we continue the line of research on the complexity of distributions (Viola, Journal of Computing 2012), and study samplers defined by low degree polynomials. An $n$-tuple $\mathcal{P} = (P_1,\dots, P_n)$ of functions $P_i \colon \mathbb{F}_2^m \to \mathbb{F}_2$ defines a distribution over $\{0,1\}^n$ in the natural way: ... more >>>
The partial derivative method is a central tool in algebraic complexity, underlying lower bounds for multilinear formulas, bounded depth circuits, and algebraic branching programs. A key feature of this measure is its subadditivity and submultiplicativity, which are usually used to upper bound the measure. However, proving lower bounds requires bounding ... more >>>
Breaking the log-squared barrier in pseudorandom generator constructions for read-once branching programs, namely, achieving seed length $o(\log^2 n)$ for length-$n$ programs, has remained a longstanding open problem since Nisan's seminal construction.
We show that breaking this barrier, even achieving seed length $O(\log^{3/2} n)$ (for, say, constant width), would follow from ... more >>>
