48 problems

Mézard–Montanari's conjecture. If $q\leq 4$ and $d<d_{\max}$, then there is reconstruction if and only if

Let $G=\operatorname{Sym}_n$ and let $T$ be the set of transpositions, so that $\operatorname{Sym}_n(T)$ is the corresponding Cayley graph, $B_r(\sigma)$ denotes the radius-$r$ bal…

Let $A$ and $B$ be two hypomorphic matrices, meaning that $B=\Sigma(A)$ for a hypomorphism $\Sigma$ as in the surrounding reconstruction setting. Let $\lambda_i$ be a simple eigenv…

Let $S_n$ be the permutation group on $n$ letters and let $\mathbb Z_2^n$ denote the group of diagonal sign matrices. Twisted-product refinement. The group $G(A)$ in the spectral r…

Let $A$ be a real $n \times n$ symmetric matrix. For each $i$, write $A_i$ for the matrix obtained by deleting the $i$th row and column, and let $\operatorname{eigen}(A)$ denote th…

Potts monotonicity conjecture. If reconstruction is solvable for $M_1$, then it is also solvable for $M_2$.

Consider the symmetric Potts channel $M$ on $q\geq 3$ symbols, with $b$-ary tree branching factor $b$ and second eigenvalue $\lambda_2(M)$. Potts-model below-bound conjecture. Ther…

Consider a channel reconstruction problem on a tree. Symmetric-binary optimality conjecture. The phenomenon that global majority achieves the same reconstruction threshold as maxim…

Let $M$ be a channel with second eigenvalue $\lambda_2(M)$, and let $T_b$ be the $b$-ary tree. The reconstruction problem is census-solvable when the root can be reconstructed from…

Consider the Ising model on the regular tree $T_b$. A local reconstruction algorithm is one in which each vertex scans the information stored at its descendants $\ell$ generations…

Let $K$ be an algebraically closed field, let $C$ be a smooth projective irreducible curve over $K$, and let $\mathfrak m$ be a modulus on $C$. Write $J_{\mathfrak m}(C)$ for the g…

Interior-point reconstructibility conjecture. Then $p$ is $\lambda$-reconstrucitble.

Let $V\subseteq\mathbb{R}$ with $|V|=n$, and let the known distances be distributed as in $G(V,\lambda/n)$ for a parameter $\lambda>0$. Call a subset reconstructible if every injec…

Let $V\subseteq\mathbb{R}$ be a set of $n$ points, let $G(V,p)$ be the random graph in which each possible edge is present independently with probability $p$, and call…

Benjamini and Tzalik's conjecture. There exists a reconstructible subset of $V$ of size $m/n$.

Giro, Illingworth, Michel, Powierski, and Scott's conjecture. For every fixed $\varepsilon>0$, when $p=(1+\varepsilon)/n$, one can reconstruct a subset of $V$ of size linear in $n$…

Let $n$ be a positive integer, and let $\boldsymbol{\lambda}=(\lambda_1,\dots,\lambda_\ell)$ be an integer partition of $n$. Define $\operatorname{pre}_2(\boldsymbol{\lambda})$ to…

Stanley's switching reconstruction conjecture. For every $n>4$, if two graphs on $n$ vertices have the same switching deck, then they are isomorphic.

Let $n\geq 4$, and let $G_1,\dots,G_k$ be a collection of $n$-edged graphs for some $k\geq 1$. Write $\coprod_{i=1}^k\operatorname{ED}(G_i)$ for the disjoint union of their edge de…

Let $k\geqslant 3$, and let $X$ be a finite $\operatorname{CAT}(0)$ cube complex. The boundary distances are the distances between vertices on the boundary of $X$. General reconstr…

Let $k\geqslant 4$, and let $X$ be a finite $\operatorname{CAT}(0)$ cube complex admitting an embedding in $\mathbb{R}^k$. The boundary distances are the distances between vertices…

Let $G=H_n^d$ be the $d$-dimensional $n$-lattice, and let the deck consist of all its $d$-dimensional $k$-subgrids. A random $r$-colouring of $G$ is called reconstructible if it ca…

Let $k\geq 1$ and let $T\in\operatorname{YT}(n)$, where $n\geq k+4$. Here $\operatorname{mM}_k(T)$ denotes the multiset of $k$-minors of the standard Young tableau $T$. Multiset re…

Let $k\geq 2$ and let $T\in\operatorname{YT}(n)$, where $n\geq k^2+2k$. Here $\operatorname{M}_k(T)$ denotes the collection of $k$-minors of the standard Young tableau $T$. Reconst…

Sharp threshold conjecture. The threshold for the existence of a reconstructible set of size linear in $n$ is sharp and occurs at