72 problems

Let $k$ be the order of a tensor, and consider noisy tensor completion for an order-$k$ tensor of dimension parameter $n$. A polynomial-time algorithm is an algorithm whose running…

In the single-spiked tensor model, let $N$ be the dimension and $p$ the tensor order. Consider local algorithms initialized randomly, as well as Sum-of-Squares (SoS) and spectral m…

Minimax lower-bound conjecture. For distributionally robust reinforcement learning, the minimax lower bound on the number of samples is still

Let $Y=AX+E$ with $Y\in\mathbb{R}^{n\times p}$, $A\in\mathbb{R}^{m\times n}$, and $X\in\mathbb{R}^{m\times p}$, where $p\geq\max\\{n,m\\}$ and typically $m\geq n$. In the square no…

Cryo-EM sample-complexity conjecture. If $R\geq 3$ is large enough, then the minimal number of observations required for accurate recovery of the $\operatorname{O}(n)$ orbit of $f$…

In tabular reinforcement learning with planning horizon $H$, consider any algorithm seeking an $\epsilon$-optimal policy when the total reward is bounded by $1$. Jiang et al.'s con…

Let mutation matrices be governed by a single order parameter $\theta$, and let $\theta(e)$ denote the parameter of the mutation matrix $M^e$ on edge $e$. Consider the Markov rando…

In the realizable PAC setting, split a labeled sample into three equal blocks and train one independently chosen consistent classifier on each block. The majority-of-three conjectu…

Effective-dimension conjecture. The relevant sample complexity for the second kernel ridge regression fit is governed by $d_{\mathrm{eff}}$. This prediction is motivated by an anal…

Let $d$ denote the ambient dimension, and consider the semi-parametric nonlinear regression setting in which the covariate-target relation is a linear dimensionality reduction foll…

Tight measurement complexity conjecture. The lower bound can be extended to every

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

A cutting-plane learning problem considers candidate cuts evaluated by a gap-closed score, with attention restricted to cuts that cut off the current fractional solution. Gap-close…

Let $F$ be a class of functions, let $D$ denote the unit ball of $L_2(\mu)$, and let $r_{\mathbb{Q}}(\kappa)$ and $r_{\mathbb{M}}(\kappa)$ be the Gaussian fixed points defined by ……

Conjecture on improving $\alpha$. A smaller function $\alpha$ may be sufficient for the cited inequalities to hold, so that the resulting improvement could be carried over to the p…

Let $\boldsymbol{F}=\{F_i\}_{i\in[n]}$ be $n\geq1$ asymmetric quasi-regular valuation distributions, let $\varepsilon\in(0,1)$, and define truncated distributions…

Let asymmetric regular and quasi-regular buyers be given valuation samples, and let the Empirical Myerson Auction be the auction learned from those samples to approximate Bayesian…

Aden-Aden-Arieli et al.'s sample-complexity conjecture. Only

Uniformly mixing complexity conjecture. Theorem should also imply an optimal complexity of $\widetilde{O}(SA\frac{\tau_{\mathrm{unif}}}{\varepsilon^2})$ for this setting by an anal…

Let VRCQ denote the variance-reduced cascade Q-learning algorithm for estimating the optimal Q-function in a discounted Markov decision process, and let $\mathcal{U}$ be its action…

Classical-shadow rate conjecture. The correct rate for classical shadows is

Let $H(\boldsymbol{\nu},\epsilon)$ denote the instance-dependent complexity appearing in the analysis of the adaptive algorithm $\adaptt{}$, and let $\alpha>1$ be an algorithmic hy…

In the edge deletion model, let $p_v=1$ and $p_e=1/2$, and consider reconstructing an arbitrary $n$-vertex graph from noisy random subgraphs. Noisy graph reconstruction conjecture.…

Sample-complexity conjecture. A tighter lower bound exists for this estimation problem, matching the upper bound of Ramsay et al.

Coverability coefficient conjecture. The coverability coefficient of the underlying MDP and policy class should characterize the instance-dependent complexity of agnostic reinforce…