11 problems

For every $T$-query quantum algorithm $A$, there is a polynomial $p$ such that, for every $\epsilon,\delta>0$, there exists a classical randomized query algorithm $C$ making at mos…

Aanderaa–Karp–Rosenberg conjecture. Every nontrivial monotone graph property is elusive.

Let $A\in\binom{[n]}{n/2}$, and define \textit{Disc-\max-}d(A)=1 if and only if … Equivalently, if $disc(j)$ is the signed discrepancy of the prefix $[j]$, then…

Active clustering query complexity conjecture. The average number of membership queries required is $(1+o(1))\sum_{i=1}^k i p_i n$. This conjecture concerns the optimal average que…

Meng–Lin–Yang's conjecture. With these definitions,

Generalized uniqueness conjecture. The ground-truth clustering ${\cal C}$ is the only valid clustering consistent with the entire query matrix.

Let $k=2$, let $\bfX\in\{0,1\}^n$ be the label vector, and let a querying scheme use $m$ same cluster' queries, each involving two elements ($\Delta=2$). A scheme is $(1-\delta)$-g…

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

Let $E$ be a finite ground set, let $\mathcal{F}\subseteq 2^E$ be a set system, and let $G\subseteq \operatorname{Symm}_E$ be a symmetry group acting transitively on $E$. Assume th…

Let a graph or digraph property be monotone if it is preserved under deletion of edges or arcs, and let a property be non-trivial if it is neither always true nor always false. A p…

Pyramid path-search conjecture. If $s_l=1+2+\ldots+l$ for some $l$, then