35 problems

Percolation conjecture. For $m\geq 4$, the configuration percolates with positive probability.

Let a communication graph be a sufficiently large complete graph, and let two distinct tokens perform independent random walks on it. A clairvoyant adversary, or demon, controls th…

HRT's conjecture. The bound can be improved, perhaps even to

Activation-function normalization conjecture. The activation function normalizes \tilde{\underaccent{\bar}{j}} to an interval close to the latent alphabet…

Let $\mathcal{H}$ be a finite graph, and consider the localized transfer principle for distributed graph-coloring algorithms via the labeling spaces…

Let $T_{\textnormal{star}}$ denote the time-complexity bound for decentralized stochastic optimization on the star graph described above, with heterogeneous worker computation time…

Consider the distributed recoloring problem for toroidal grids in the LOCAL model, where a schedule transforms an input proper coloring into a target coloring. The constant-round t…

Let $G$ be a graph, let $v(G)$ denote its number of vertices, and let $B_c[v]$ be the subgraph induced by the vertices at distance at most $c$ from $v$. For a positive integer $c$,…

The analog MatDot scheme uses evaluation points on the unit circle, and for each colluding set $\mathcal{X}$ the matrices $\Gamma_a$ and $\Sigma_{a'}$ determine the quantity…

Lower-bound conjecture. If

Angluin's conjecture. The graphs $G$ and $H$ have a common finite cover.

Subexponential-growth equivalence conjecture. The equality established on paths should extend to every graph family of subexponential growth:

Randomness-elimination conjecture. Randomness does not help in graphs of subexponential growth: in this setting, randomized local algorithms should not have an essential advantage…

The deterministic Lovász Local Lemma (LLL) problem asks for a deterministic local algorithm solving instances of the Lovász Local Lemma on graphs, where $n$ denotes the relevant in…

Let $X_1$ and $X_2$ be sources, possibly independently distributed or correlated, and let $f$ be a function whose value is to be computed from their observations. Binning inefficie…

Scheme 1 gap conjecture. For the other values of $K$, $r$ and $s$, one has

Asymptotic optimality conjecture. For MDS-XSTPIR, the rate

Let $\alpha$ be the angle between the two lines in the averaged Kaczmarz method, and define … Here $\Omega$ is the relaxation-parameter value at which the larger eigenvalue of the…

Let the source variables be quantized using a quantizer satisfying the assumptions made in the paper, and let performance refer to the protocol performance measured by its error pr…

MP-AMP cost conjecture. The total computation and communication cost scales as

Let $G_i$ be unlabeled networks, let $k\geq 3$, and let $\mathcal F(G_i,k)$ denote the corresponding system of $k$ oblivious mobile robots. Let $G_i^\ast$ be the quotient graph ass…

Let $G$ be a network and let $k\geq 1$. Write $\mathcal F(G,k)$ for the system of $k$ oblivious mobile robots on $G$, and write $\preceq$ for the computational-capability preorder.…

Let ${\mathsf{u}}$ and ${\mathsf{v}}$ be binary variables satisfying the Markov chain … Here $\binEnt{t}=-t\log t-(1-t)\log(1-t)$ denotes the binary entropy and $a*b=a(1-b)+(1-a)b$…

Consider Herman's token process on a cycle of $N$ nodes, started from any initial configuration with an odd number of tokens, and let $E(\mathbf{T})$ be the expected time until one…

Consider a cycle of $N$ nodes with an odd number of tokens. At each step, each token independently moves to its clockwise neighbor or stays at its position with probability…