Realization of sign matrices in Euclidean spaces

Noga Alon, Tel Aviv University and IAS, Princeton

October 20, 2015

The signrank of an $N$ by $N$ real matrix $A$ with nonzero entries is the minimum dimension $s$ so that there are hyperplanes $h_i$ through the origin and points $p_j$ in $R^s$ such that $p_j$ lies in the positive side of $h_i$ if $A_{ij}=+1$, and in its negative side if $A_{ij}=-1$.

The study of this notion combines combinatorial, algebraic, geometric and probabilistic techniques with tools from real algebraic geometry, and is related to questions in Discrete Geometry, Communication Complexity, Computational Learning and Asymptotic Enumeration. I will discuss the topic focusing on recent results in joint work with Moran and Yehudayoff, and mention some intriguing open problems.