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 show the following hardness results for monotone learning and approximation of monotone circuit size:
1. Under the Randomised Exponential-Time Hypothesis (rETH), it requires time $n^{\Omega(\log n)}$ to PAC-learn monotone formulas with $n$ input bits and size $s(n) = n$ by monotone circuits of size $n^{(\log n)^{1-\epsilon}}$, for every $\epsilon ... more >>>
We prove that every De Morgan formula with $n$ leaves has a pointwise $1/3$-approximating real polynomial of degree $O(\sqrt n)$ and coefficient $\ell_1$-norm $2^{O(\sqrt n)}$. The standard approximate-degree theorem for formulas gives the same degree bound, but only yields the weaker coefficient estimate $2^{O(\sqrt n\log n)}$.
Our proof constructs, for ... more >>>
We show that under a plausible number-theoretic conjecture, for any constant $s$ there exists an $s$-server private information retrieval (PIR) protocol that on an $n$-bit database requires communication $\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$. Previous constructions attaining the same communication required $2^{O(s)}$ servers. Our number-theoretic conjecture is implied by existing conjectures, ... more >>>
