Subexponential NOF communication complexity conjecture for exactly-NN

In the three-player number-on-forehead (NOF) model, let the exactly-NN problem be the task of determining whether the sum of the players' hidden inputs equals NN. Its communication complexity is measured as a function of NN. Exactly-NN communication conjecture. The NOF communication complexity of exactly-NN is o(logN)o(\sqrt{\log N}). Possibly it is much smaller, even as small as (loglogN)O(1)(\log\log N)^{O(1)}. This conjecture would yield improved lower bounds for the corresponding three-variable corner-free-set density in additive combinatorics, and the paper presents the quantitative additive-combinatorial formulation below as a translation of this claim.

Sources & referencesView supporting material

Primary source

Nati Linial and Adi Shraibman, “Larger Corner-Free Sets from Better NOF Exactly-N Protocols”, arXiv:2102.00421 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.