Abstract
Margin (aka discrepancy) and sign-rank (aka dimension complexity) are two fundamental complexity measures of boolean matrices with many applications in communication complexity, machine learning, etc. We discuss two basic questions regarding the relationship between sign-rank and margin.
Question one: Can margin be lower bounded by a function of sign-rank? Question two: Can sign-rank be upper bounded as a function of margin?
We discuss reinterpretations of these questions which come up naturally in communication complexity, machine learning, and dimensionality reduction via the Johnsson-Lindenstrauss theorem.
We use different tools to give strong negative answers to the above questions, the first using Fourier analysis and the second via the Borsuk Ulam theorem.
Based on joint works with Hamed Hatami, Shachar Lovett, and Xiang Meng.