Abstract
Threeplayer Number On the Forehead communication may be thought of as a threeplayer Number In the Hand promise model, in which each player is given the inputs that are supposedly on the other two players' heads, and promised that they are consistent with the inputs of the other players. The set of all allowed inputs under this promise may be thought of as an order3 tensor. We surprisingly observe that this tensor is exactly the matrix multiplication tensor, which is widely studied in the design of fast matrix multiplication algorithms.
Using this connection, we prove a number of results about both Number On the Forehead communication and matrix multiplication, each by using known results or techniques about the other. For example, we show how the Laser method, a key technique used to design the best matrix multiplication algorithms, can also be used to design communication protocols for a variety of problems. We also show how known lower bounds for Number On the Forehead communication can be used to bound properties of the matrix multiplication tensor such as its zeroing out subrank. Finally, we substantially generalize known methods based on slicerank for studying communication, and show how they directly relate to the matrix multiplication exponent ω.
BibTeX  Entry
@InProceedings{alman_et_al:LIPIcs.CCC.2023.16,
author = {Alman, Josh and B{\l}asiok, Jaros{\l}aw},
title = {{Matrix Multiplication and Number on the Forehead Communication}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {16:116:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772822},
ISSN = {18688969},
year = {2023},
volume = {264},
editor = {TaShma, Amnon},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18286},
URN = {urn:nbn:de:0030drops182861},
doi = {10.4230/LIPIcs.CCC.2023.16},
annote = {Keywords: Number on the forehead, communication complexity, matrix multiplication}
}
Keywords: 

Number on the forehead, communication complexity, matrix multiplication 
Collection: 

38th Computational Complexity Conference (CCC 2023) 
Issue Date: 

2023 
Date of publication: 

10.07.2023 