The tight log-rank conjecture for AND-functions

Let f:{0,1}n{0,1}f: \{0,1\}^n \to \{0,1\} be a Boolean function, and let spar(f)=r\operatorname{spar}(f)=r be its sparsity, namely the number of nonzero coefficients in its unique multilinear polynomial over the reals. Let f(x,y)=f(x1y1,,xnyn)f_{\land}(x,y)=f(x_1y_1,\ldots,x_ny_n), and write P-dt(f)\mathrm{P}^{\land\text{-dt}}(f) for deterministic AND-decision-tree depth. Tight log-rank conjecture. One should have

P-dt(f)poly(logr).\mathrm{P}^{\land\text{-dt}}(f)\leq \operatorname{poly}(\log r).

The conjecture would remove the extraneous logn\log n factor from the paper's deterministic log-rank theorem and would also imply a tighter lifting theorem for AND-functions. The source gives no resolution evidence.

Sources & referencesView supporting material

Primary source

Alexander Knop, Shachar Lovett, Sam McGuire and Weiqiang Yuan, “Log-rank and lifting for AND-functions”, arXiv:2010.08994 (2020).

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.