Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank

Nathaniel Harms, Viktor Zamaraev

We prove a characterization of the structural conditions on matrices of sign-rank 3 and unit disk graphs (UDGs) which permit constant-cost public-coin randomized communication prot…