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 give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits ... more >>>
Given two symbolic matrices $X$ and $Y$ of dimensions $m\times n$ and $n\times m$, respectively, the *rank principle* states that when $m = n+1$ and $A$ is a scalar matrix of rank $n+1$, the equation $XY = A$ is unsatisfiable. When $m$ is arbitrarily larger than $n$ and $A$ has ... more >>>
We extend the recent work of Reis and Rothvoss on sparsifying sums of $\ell_1$ norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. As our main result, we prove that for any $\varepsilon > 0$ and centrally symmetric, convex sets $C_1, \ldots, C_m\subseteq\mathbb R^n$ ... more >>>
