ECCC - Gabriel Hart
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > GABRIEL HART:
All reports by Author Gabriel Hart:

TR26-306 | 4th November 2026
Gabriel Hart, Kaave Hosseini

Exponential Separation of Sign-Rank and Margin Complexity

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




ISSN 1433-8092 | Imprint