38 problems

Low et al.'s conjecture. The optimal query complexity for block encoding $e^{-At}$ should scale as

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…

Let $d_1$ and $d_2$ be the input and output dimensions of a quantum channel, let $r$ be its Choi rank, and let $\varepsilon$ be the tomography error. Near the boundary…

Let $\mathcal{E}$ be a quantum channel with input dimension $d_1$, output dimension $d_2$, and Choi rank $r$, and let $\varepsilon$ denote the tomography error. Mele–Bittel's optim…

Let $d$ be the dimension of the quantum system and let $\varepsilon$ be the target estimation error. In the inverse-free query model, one has access to a state-preparation unitary…

Let $d$ be the dimension of the quantum system and let $\varepsilon$ be the target estimation error. In the inverse-free query model, one has access to a state-preparation unitary…

Let a linearly parameterized matrix family have dimension $q$, and let $\epsilon>0$. A pure relative-error approximation has error measured relative to the relevant optimum in the…

Let $\mathcal{F}$ be a finite family of structured matrices, and let $\epsilon>0$. A query is an evaluation involving the unknown matrix and a query vector, as in the paper's matri…

Query-optimality conjecture. The reconstruction methods developed for these classes are all optimal: no reconstruction algorithm for the respective classes can use fewer queries th…

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

Quantum gradient-estimation conjecture. There exists a quantum algorithm for this task whose query complexity matches the lower bound established in the paper. The paper gives a qu…

Tightness conjecture. This lower bound is tight: quantum algorithms for solving linear programs to constant precision should require only $\widetilde{O}(\sqrt{nd})$ row queries. Th…

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…

Let $E_k(n)$ denote the extremal excess in the query complexity problem for Boolean functions on the slice $\binom{[n]}{k}$. The notation $E_k(n)=O(1)$ means that this excess is bo…

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…

Gaussian sampling lower-bound conjecture. Theorem should hold for all $\kappa$ for which $\sqrt{\kappa} \log d \le d$; that is, any sampler for $d$-dimensional Gaussians with condi…

First-order lower-bound conjecture. Can one prove an $\Omega(1/\varepsilon^2)$ complexity lower bound for randomized algorithms which only make first-order queries in dimension two…

Let $R$ be a non-trivial graph property on a finite vertex set $V$. In the associated query game, a seeker asks whether individual edges belong to the graph, and the game ends when…

Consider the affine-constrained case in which ${\mathbf{c}}({\mathbf{x}})={\mathbf{A}}{\mathbf{x}}-{\mathbf{b}}$, and let $h$ denote the nonsmooth term in the composite objective.…

Leftover-regime conjecture. No polynomial-time algorithm exists for detecting the planted subgraph.

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 $d$ be the dimension and let $\varepsilon$ satisfy … Consider highly parallel algorithms for non-smooth convex optimization, where depth measures the number of sequential compu…

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…

Let $T$ be a tree on $n$ vertices, and let $m(T)$ denote the minimum number of edge queries needed to determine whether the vertex coloring has a majority. Lower-bound conjecture f…