BIBLIOS

Document type
Conference papers

Document subtype
Full paper

Title
An Improved Protocol for ExactlyN with More Than 3 Players

Participants in the publication
Lianna Hambardzumyan (Author)
Toniann Pitassi (Author)
Suhail Sherif (Author)
Dep. Matemática
Morgan Shirley (Author)
Adi Shraibman (Author)

Summary
The ExactlyN problem in the number-on-forehead (NOF) communication setting asks k players, each of whom can see every input but their own, if the k input numbers add up to N. Introduced by Chandra, Furst and Lipton in 1983, ExactlyN is important for its role in understanding the strength of randomness in communication complexity with many players. It is also tightly connected to the field of combinatorics: its k-party NOF communication complexity is related to the size of the largest corner-free subset in [N]^{k-1}. In 2021, Linial and Shraibman gave more efficient protocols for ExactlyN for 3 players. As an immediate consequence, this also gave a new construction of larger corner-free subsets in [N]². Later that year Green gave a further refinement to their argument. These results represent the first improvements to the highest-order term for k = 3 since the famous work of Behrend in 1946. In this paper we give a corresponding improvement to the highest-order term for k > 3, the first since Rankin in 1961. That is, we give a more efficient protocol for ExactlyN as well as larger corner-free sets in higher dimensions. Nearly all previous results in this line of research approached the problem from the combinatorics perspective, implicitly resulting in non-constructive protocols for ExactlyN. Approaching the problem from the communication complexity point of view and constructing explicit protocols for ExactlyN was key to the improvements in the k = 3 setting. As a further contribution we provide explicit protocols for ExactlyN for any number of players which serves as a base for our improvement.

Editor(s)
Venkatesan Guruswami


Event
15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Publication Identifiers

Address
Berkeley, CA, USA

Publisher
Schloss-Dagstuhl - Leibniz Zentrum für Informatik


Keywords
combinatorics communication complexity number on forehead multidimensional szemeredi's theorem corners theorem

Download