39 problems

The Fooling-Set-Submatrix problem takes integers $n,m$ and an $m\times m$ $0/1$-matrix $A$ as input, and asks whether $A$ contains a fooling-set submatrix of size $n$. NP-hardness…

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…

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 $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 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 an $n\times n$ Boolean matrix, and let randomized communication complexity mean the public-coin randomized communication complexity of $M$. A submatrix is monochromatic…

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…

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

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…

Let $\mathcal M$ be a sequence of $n \times n$ Boolean matrices. For a sequence of matrices, let $\operatorname{cl}(\mathcal M)$ be the set of all square submatrices of matrices in…

Quantum Hidden Hypermatching upper-bound conjecture. If $t,r>2$, there is a protocol for $r\text{-}{\mathsf{HH}}(\alpha,t,n)$ using

In the three-player number-on-forehead (NOF) model, let the exactly-$N$ problem be the task of determining whether the sum of the players' hidden inputs equals $N$. Its communicati…

Almost cross-disjointness conjecture. For every fixed $\epsilon>0$, if $\mathcal A$ and $\mathcal B$ are $\epsilon$-almost cross-disjoint, then there exist…

Parallel 2-partition conjecture. Then

Log-rank conjecture. For every function $f: \mathcal X \times \mathcal Y \to \{0,1\}$,

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…

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

Polylogarithmic-party hardness conjecture. There is no protocol for the $k$-party $t$-tuple interleaved group product over $G$ with $k=\log^c t$ parties and communication…

For positive integers $n$ and $k$, let $Part_{n,k}$ denote the problem of determining whether pairwise disjoint sets $S_1,\ldots,S_k$ form a partition of $[n]$, and let…

Closure-size conjecture. There are constants $c_1,c_2>0$ such that, if

Let $A\subseteq S^{n-1}$ be a measurable subset with $\sigma_{n-1}(A)\geq e^{-c\sqrt{n}}$. For a subspace $H\subseteq\mathbb{R}^n$ of dimension $\lfloor n/2\rfloor$, let…

Let $Pi$ be an interactive protocol with a sufficiently non-regular, for example pseudo-random, communication order, and let $Pi'$ be a non-adaptive protocol whose communication or…

Sparse estimation tradeoff conjecture. If some protocol estimates the mean for any distribution $P\in\mathcal{P}_s$ with mean-squared loss $R$ and communication cost $C$, then