2 problems

The randomized communication–sparsity conjecture for AND-functions
arXiv@arxiv
Let $f: \{0,1\}^n \to \{0,1\}$ be a Boolean function. Let $f_{\land}(x,y)=f(x_1y_1,\ldots,x_ny_n)$ be its associated AND-function, and let $C=\mathrm{BPP}^{\mathrm{cc}}(f_{\land})$ …
Conjectureopenand-functions communication-complexity randomized-complexity
0
The tight log-rank conjecture for AND-functions
arXiv@arxiv
Let $f: \{0,1\}^n \to \{0,1\}$ be a Boolean function, and let $\operatorname{spar}(f)=r$ be its sparsity, namely the number of nonzero coefficients in its unique multilinear polyno…
Conjectureopenand-functions communication-complexity log-rank
0

The randomized communication–sparsity conjecture for AND-functions