Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AVERAGE MARGIN:
Reports tagged with Average Margin:
TR22-079 | 25th May 2022
Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao

#### Lower Bound Methods for Sign-rank and their Limitations

The sign-rank of a matrix $A$ with $\pm 1$ entries is the smallest rank of a real matrix with the same sign pattern as $A$. To the best of our knowledge, there are only three known methods for proving lower bounds on the sign-rank of explicit matrices: (i) Sign-rank is ... more >>>

ISSN 1433-8092 | Imprint