check
HD-Combinatorics: Adi Shraibman, "The communication complexity of high-dimensional permutations" | Einstein Institute of Mathematics

HD-Combinatorics: Adi Shraibman, "The communication complexity of high-dimensional permutations"

Date: 
Mon, 14/05/201810:00-10:50
Location: 
Feldman Buildng, Givat Ram
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.