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 develop a topological framework for proving lower bounds on sign-rank via $\mathbb{Z}_2$–equivariant topology, and use it to resolve the sign-rank of the Gap Hamming Distance problem up to lower-order terms.
For every (partial) sign matrix $A$, we associate a free $\mathbb{Z}_2$–simplicial complex $S(A)$ and show that sign-rank of $A$ ... more >>>
Given a propositional proof system $P$, we may define a formula $\text{Prf}^P_s(F)$ which is satisfiable if and only if the formula $F$ has a length $\leq s$ refutation in $P$. These formulas have received much attention in recent years due to their fundamental nature --- if a powerful proof ... more >>>
For an arbitrary family of predicates $\mathcal{F} \subseteq \{0,1\}^{[q]^k}$ and any $\epsilon > 0$, we prove a single-pass, linear-space streaming lower bound against the gap promise problem of distinguishing instances of Max-CSP$({\mathcal{F}})$ with at most $\beta+\epsilon$ fraction of satisfiable constraints from instances of with at least $\gamma-\epsilon$ fraction of satisfiable ... more >>>
