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 prove that for all $\varepsilon>0$, there exists a positive integer $k$ such that given a $4$-to-$1$ Game $\Psi$ with alphabet size at most $k$, it is NP-hard to distinguish between the case that val$(\Psi)=1$ and the case that val$(\Psi)\leq \delta$. This confirms the $4$-to-$1$ Games Conjecture from [Khot, CCC ... more >>>
We use this framework to construct HSGs for read-once CNFs and read-once CNFs with parities. For formulas on $n$ variables with density at least $\varepsilon$, our generators use $O(\log(n/\varepsilon))$ seed bits. This bound is optimal up to a constant factor. Applying the hitting reduction of Gopalan, Meka, Reingold, Trevisan, and ... more >>>
The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about ... more >>>
