Subexponential NOF communication complexity conjecture for exactly-
Subexponential NOF communication complexity conjecture for exactly-
In the three-player number-on-forehead (NOF) model, let the exactly- problem be the task of determining whether the sum of the players' hidden inputs equals . Its communication complexity is measured as a function of . Exactly- communication conjecture. The NOF communication complexity of exactly- is . Possibly it is much smaller, even as small as . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.