36 problems

For $m$ fermionic modes, let $\mathcal H_m$ be the corresponding Hilbert space, let $\mathcal G_m^\pm$ denote the pure fermionic Gaussian states, and let … be the projector definin…

Quadratic sample-complexity conjecture. The quantum sample complexities of von Neumann entropy estimation, trace distance estimation, and fidelity estimation are

Ordered matrix removal conjecture. For every $k\times k$ binary matrix $A$ and every $\varepsilon>0$, there is a $\delta=\delta(k,\varepsilon)=\operatorname{poly}(\varepsilon)>0$ s…

Let $F$ be an ordered graph, meaning a graph equipped with a linear order on its vertices. An ordered forest is an ordered graph whose underlying graph is a forest, and the core of…

Let $C_4$ denote the cycle with four vertices, and let $q_{\text{ind-}C_4\text{-free}}(\varepsilon)$ be the query complexity for testing induced $C_4$-freeness. Induced $C_4$-freen…

Given a natural number $k$, an object $B$, and $n$ points, the task is to determine with high probability whether all the points are contained in $k$ translated copies of $B$, or e…

Let $S$ be a finite generating set and let $E$ be a finite set of relators such that … is a finitely presented amenable group. Let the Følner function of $\Gamma$ measure the sizes…

Conjectured behavior of $f$. For $\mathbb{GOF}$ in $\mathcal{I}_d$, $f$ should behave like $p^2/s^2$, while for $\mathbb{EOF}$ it should behave like $p^2/s$.

Bhattacharyya–Grigorescu–Shapira conjecture. Every linear-invariant, semi subspace-hereditary property is testable.

Induced arithmetic removal conjecture. A statement analogous to the induced arithmetic removal theorem for finite collections of $r$-colored complexity $1$ patterns over finite-dim…

Fix a Boolean function $phi$ such that the only exact solutions to the corresponding functional equation are dictatorships. Consider Boolean functions $f$ that are approximate solu…

Let $\theta$ denote the exponent implicit in the notation $\delta^{\Theta(1)}$, and let $epsilon$ and $delta$ be the error parameters in Theorem. Polynomial-dependence conjecture.…

Gishboliner–Shapira conjecture. The class of chordal graphs is easily testable; equivalently, the current testability query-complexity bound $2^{(1/\epsilon)^c}$ can be improved to…

2-local testability conjecture. Any 2-local property is testable with

Erdős's removal conjecture. If $G$ is $\varepsilon$-far from being $k$-colorable, then a uniformly sampled set of $C_k(\varepsilon)$ vertices spans a non-$k$-colorable subgraph wit…

Ordered binary matrix removal lemma. For any finite family $\mathcal{F}$ of ordered binary matrices and any $\epsilon > 0$ there exists $\delta = \delta(\mathcal{F}, \epsilon)$ suc…

A semi-algebraic graph property ${\cal P}$ is specified by an integer $k\geq 1$, real polynomials $f_1,\dots,f_t\in\mathbb{R}[x_1,\dots,x_{2k}]$, and a Boolean function…

Goldreich and Ron considered testing expansion in bounded-degree graphs by selecting a random node and testing whether random walks from it approach the uniform distribution on the…

Logarithmic lower-bound conjecture. Monotonicity testing in the ${\sf EVAL}$ model has query complexity

The strong USP capacity is the largest constant $c$ for which there exist $n$-dimensional strong uniquely solvable puzzles of size $(c-o(1))^n$ for infinitely many $n$. Cohn–Kleinb…

An affine-invariant property $\mathcal P$ is subspace hereditary if, whenever $f:\mathbb{F}^n\to [R]$ satisfies $\mathcal P$, the restriction of $f$ to every affine subspace of…

Let $M\in\mathbb F_2^{m\times k}$ and $\sigma\in\\{0,1\\}^k$. A function $f:\mathbb F_2^n\to\\{0,1\\}$ is $(M,\sigma)$-free if there is no $k$-tuple of row vectors…

Let $\mathcal{A}$ be a collection of induced affine constraints over $\mathbb{F}_p$. For a set of linear forms, its Cauchy–Schwarz complexity is the least $s$ such that, for every…

Let $p$ be a prime, and let an affine-invariant property $\mathcal{P}$ assign to functions $f:\mathbb{F}_p^n\to [R]$ a property that is preserved under affine transformations. The…

Characterization conjecture. Partially symmetric functions are essentially the only functions for which isomorphism testing can be performed with a constant number of queries.