13 problems

USPN conjecture. For any permutation $\pi$ of any length, $\pi$-freeness has a non-adaptive one-sided $\varepsilon$-test making

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…

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…

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…

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

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 $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…

Let $\mathcal{F}$ be a possibly infinite set of systems of induced equations, and let a Boolean function be $\mathcal{F}$-free when it contains no induced solution of any system in…

Let $f:\mathbb{F}_2^n \to \mathbb{F}_2^m$ be a function, and let $\epsilon$ measure the probability that it satisfies the additive homomorphism equation on uniformly sampled…

Square-root query-complexity conjecture. For every $H$, being $H$-minor free can be tested with one-sided error using $\tilde{O}(\sqrt{n})$ queries, where $n$ is the number of vert…