Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
Nathaniel Harms, Viktor Zamaraev · Society for Industrial and Applied Mathematics eBooks · 2024
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 protocols. Therefore, under these conditions, these graphs also admit implicit representations.