
PreviousNext
We construct an explicit family of total sign matrices whose sign-rank is exponentially larger than their margin complexity. Previously, no superpolynomial separation was known for total matrices. In particular, we give a quantitative answer to a question of Linial, Mendelson, Schechtman, and Shraibman (Combinatorica, 2007), who asked whether the logarithmic ... more >>>
In Hrubeš' Algebraic Monotone Calculus AMC a DNF tautology $A$ is proved by a monotone arithmetic circuit computing $\chi(A)-\epsilon\cdot\chi(1)$ for some $\epsilon>0$, where $\chi(A)$ is the set-multilinear polynomial whose coefficient at $\mathbf x^{\sigma}$ counts the terms of $A$ satisfied by $\sigma$, and $\chi(1)=\prod_{i\le n}(x_i^0+x_i^1)$. Proof size is circuit size, and ... more >>>
For infinitely many rates $R \in (0,1)$, we show that full-length Reed-Solomon codes over fields of low characteristic can contain super-polynomially many codewords in a Hamming ball of radius just exceeding the Johnson radius. Over prime fields, we exhibit full-length Reed-Solomon codes of constant rate $R$ with polynomially many codewords ... more >>>
PreviousNext