90 problems

Log-rank conjecture. For any Boolean function $f$, $\operatorname{cc}(f)$ is bounded above by a polynomial in $\log r$.

Let $X$ and $Y$ be finite sets, and let $f:X\times Y\rightarrow \{-1,1\}$ be a Boolean function whose communication matrix has rank $r$. Write $\operatorname{CC}^{\det}(f)$ for its…

Let $m\geq 3$ and $0<\rho<1$. Consider two measurable partitions $\Omega_1,\ldots,\Omega_m$ and $\Omega'_1,\ldots,\Omega'_m$ of $\mathbb{R}^{n+1}$ with…

Shift-strategy characterization conjecture. Every optimal strategy is a shift strategy.

Let $F$ be a 2-party function, and let $\rank_{\eps'}(F)$ denote its approximation rank at error parameter $\eps'$. Let $\bfR_\eps(F)$ be the $\eps$-error randomized communication…

Information-order conjecture. If the nodes which have more information communicate first, then this brings down the overall communication complexity.

Let $X_1,\ldots,X_k$ and $Y$ be sets, let $f\colon X_1\times\cdots\times X_k\to Y$ be a function, and let ${\cal G}\left<f,q,l\right>$ denote the generalized Ulam game in which Pau…

Adaptive field codes represent smooth transport fields using only the cells with nonzero perturbation, while certified sampler protocols may also require residual exact-marginal co…

Let $\theta\in\mathbb{R}^d$ be an $s$-sparse mean vector in the horizontal-split distributed mean-estimation model, where each of $K$ machines holds a subset of $m$ independent sam…

Let $\operatorname{GHD}_k^n$ be the partial sign matrix for the gap Hamming distance problem, and let $A$ be any total sign matrix obtained by replacing every $*$ entry of…

Let $f:{0,1}^{2n}\to\{\pm1\}$, and consider the Multiphase Problem in which $m$ vectors $S_1,\ldots,S_m\in\{0,1\}^n$ are preprocessed, an update vector $X\in\{0,1\}^n$ modifies the…

Let $M$ be a Boolean matrix, and let a monochromatic rectangle be a submatrix all of whose entries have the same value. Let ${\mathrm{r}}(M)$ denote the rank of $M$ over the reals,…

Let $\mathcal{S}=\{S_1,\ldots,S_m\}$ and $\mathcal{T}=\{T_1,\ldots,T_n\}$ be families in $2^{[d]}$, and suppose that $(\mathcal{S},\mathcal{T})$ is $\{a,b\}$-cross-intersecting, me…

Let $M$ be a Boolean matrix. Let ${\mathrm{p}}(M)$ be its partitioning number, and let $\operatorname{srr}(M)$ be the minimum number of primitive matrices needed to express $M$ as…

Let $M$ be a Boolean matrix. Write ${\mathrm{r}}(M)$ for its rank over the reals, ${\mathrm{p}}(M)$ for its partitioning number, and let the communication complexity of $M$ be the…

Let $M$ be an $m\times n$ Boolean matrix, and let $\gamma_2(M)$ denote its $\gamma_2$-norm. A blocky matrix is a blow-up of a permutation matrix. Bounded $\gamma_2$-norm decomposit…

Let $M$ be a Boolean matrix, and call a submatrix monochromatic if it is all zeros or all ones. The normalized trace norm is the trace norm normalized by the matrix dimensions, as…

Let $M$ be an $n\times n$ Boolean matrix, and let randomized communication complexity mean the public-coin randomized communication complexity of $M$. A submatrix is monochromatic…

Unbiased-compressor lower-bound conjecture. The lower bounds proved in the paper should also hold for the entire family of unbiased compressors.

Let $M$ be an $m\times n$ binary matrix, with entries in $\{0,1\}$, and let $\gamma_2(M)$ denote its factorization max-norm. A submatrix is obtained by restricting $M$ to selected…

Let $M$ be a Boolean matrix, meaning a matrix with entries in $\{0,1\}$. Its factorization max-norm is denoted by $\gamma_2(M)$, and let $\operatorname{bl}(M)$ be the minimum numbe…

Tyagi's public-communication conjecture. Any such protocol must reveal publicly at least

Lovett's conjecture. The matrix $M$ contains an all-zero square submatrix of size at least

Let a Boolean function be a function taking values in $\{0,1\}$, and let its XOR-lift be the associated communication problem obtained by evaluating the function on the coordinatew…

Let $H$ be a group, and let $a{ij} otin H$? Wait: the paper considers the number-on-forehead communication problem in which the input is a $ktimes t$ matrix $(a{ij})$ of elements o…