English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The ExactlyN problem in the number-on-forehead (NOF) communication settingasks $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 randomnessin communication complexity with many players. It is also tightly connected tothe field of combinatorics: its $k$-party NOF communication complexity isrelated to the size of the largest corner-free subset in $[N]^{k-1}$.  In 2021, Linial and Shraibman gave more efficient protocols for ExactlyN for3 players. As an immediate consequence, this also gave a new construction oflarger corner-free subsets in $[N]^2$. Later that year Green gave a furtherrefinement to their argument. These results represent the first improvements tothe highest-order term for $k=3$ since the famous work of Behrend in 1946. Inthis paper we give a corresponding improvement to the highest-order term forall $k>3$, the first since Rankin in 1961. That is, we give a more efficientprotocol for ExactlyN as well as larger corner-free sets in higher dimensions.  Nearly all previous results in this line of research approached the problemfrom the combinatorics perspective, implicitly resulting in non-constructiveprotocols for ExactlyN. Approaching the problem from the communicationcomplexity point of view and constructing explicit protocols for ExactlyN waskey to the improvements in the $k=3$ setting. As a further contribution weprovide explicit protocols for ExactlyN for any number of players which servesas a base for our improvement.

An improved protocol for ExactlyN with more than 3 players