A k-dimensional permutation is a (k+1)-dimensional array of zeros and ones, with exactly a single one in every axis parallel line. We consider the “number on the forehead" communication complexity of a k-dimensional permutation and ask how small and how large it can be. We give some initial answers to these questions. We prove a very weak lower bound that holds for every permutation, and mention a surprising upper bound. We motivate these questions by describing several closely related problems: estimating the density Hales-Jewett number, high-dimensional szemeredi theorems, constructing ruzsa-szemeredi graphs, and more.
Mon, 14/05/2018 - 10:00 to 10:50
Feldman Buildng, Givat Ram