The subspace design property for additive codes is a higher-dimensional generalization of the minimum distance property. As shown recently by Brakensiek, Chen, Dhar and Zhang, it implies that the code has similar performance as random linear codes with respect to all “local properties”. Explicit algebraic codes, such as folded Reed-Solomon ... more >>>

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 >>>