Additive-combinatorial formulation of the exactly-NN conjecture

Let ρ3(N)\rho^{\angle}_3(N) denote the maximum density of a three-variable corner-free subset in the additive-combinatorial setting used by the paper. Corner-free density conjecture. One should have

ρ3(N)2o(logN).\rho^{\angle}_3(N) \ge 2^{-o(\sqrt{\log N})}.

Possibly even

ρ3(N)2(loglogN)O(1).\rho^{\angle}_3(N) \ge 2^{-(\log\log N)^{O(1)}}.

These bounds are presented as the additive-combinatorial translation of the conjectured improvement in the NOF communication complexity of exactly-NN; the precise definition and ambient domain of ρ3(N)\rho^{\angle}_3(N) should be checked in the paper.

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.