2018
May
14

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

10:00am to 10:50am

## 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:

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: