52 problems

Let $D\subset\mathbb R^d$ be open, bounded, and convex, and let $\mathcal W$ be a renormalization class on $\overline D$. Assume that the asymptotic fixed-point equation has a uniq…

Let $D\subset\mathbb R^d$ be open, bounded, and convex, let ${\cal W}$ be a renormalization class on $\overline D$, and suppose that the asymptotic fixed-point equation in the zero…

Let $d\geq K$, let $\Delta$ be the separation parameter, and suppose the mixture means are sampled according to the prior distribution considered in the paper. Let $G^{*,sp}$ be th…

Let $n$, $d$, and $K$ be positive integers with $d\geq K$, and let $\Delta_*$ denote the separation parameter for the Gaussian-mixture clustering model. Write $a\gtrsim_{\log} b$ w…

In the Gaussian mixture clustering model, let $n$ be the number of observations, $p$ the ambient dimension, and $K$ the number of clusters. The informational threshold concerns sta…

Consider a Gaussian mixture model with $n$ observations in $\mathbb{R}^p$, a fixed number $K$ of clusters, and signal separation $\mathit{\Delta}^2$. Assume the asymptotic regime…

Let $\beta$ denote the parameter governing the clustering scale, and suppose that for a general matrix $V$ the particles rapidly converge to a lower-dimensional subspace spanned by…

Let $Q$ and $K$ be arbitrary matrices, and let $V$ be a matrix whose largest eigenvalue $\lambda_{\max}>0$ is real, with eigenspace $L$ satisfying $\mathop{\rm dim} L\geq2$. Assume…

Let $Q$ and $K$ be arbitrary matrices, and let $V$ be diagonalizable with $d$ different positive real eigenvalues. Denote its largest eigenvalue by $\lambda_{\max}$, and let $\xi$…

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…

Davis et al.'s conjecture. There does not exist a computationally efficient algorithm for general GMM that achieves the optimal misclassification rate with a linear sample complexi…

Let a capacitated vehicle routing problem be denoted by $\mathcal{CVRP}$ and a constrained centroid-based clustering problem by $\mathcal{CCBC}$. Sufficiency conjecture. It is suff…

Vu–Abbe conjecture. Vanilla spectral algorithms are themselves good clustering algorithms for the stochastic block model.

Peng et al.'s optimality conjecture. The sample complexity is optimal among efficient algorithms, up to logarithmic factors, for recovery of clusters of size…

Let $V$ be the matrix governing the self-attention dynamics on tokens $z_i(t)\in\mathbb{R}^d$, and let $k\geq 1$ be the number of eigenvalues of $V$ with positive real part. Codime…

Let $n$ points be sampled from a distribution in dimension $d>1$, and let $\mathrm{LF}$ denote the leapfrog distance between points in the resulting sample. Leapfrog-distance conje…

Let $f$ be an admissible probability density function on $\mathbb{R}^d$, with support $S$ having $K$ path-connected components, and let $n$ points be sampled according to $f$. For…

A Pareto set is the set of nondominated points arising from a multi-objective optimization problem; here, the relevant Pareto set is associated with the trade-off over a discrete s…

Consider the symmetric binary perceptron (SBP) at a positive subcritical density, where its solution space consists mostly of totally frozen isolated solutions. A cluster is a coll…

Hamming-distance-one conjecture. An analogous combinatorial property to Lemma might allow this feasible set to be shrunk from $\mathrm{Alt}(c^{t*})$ to the alternative instances wh…

Clique algorithm optimality conjecture. For an $n$-set with a random partition with probabilities $p_1,p_2,,,,,,,,,,$, the clique algorithm has minimal average complexity among all…

Polynomial-time computational conjecture. No polynomial-time method can achieve a better sample complexity than the spectral algorithm for this clustering problem.

Let $r$ denote the separation parameter for two unit balls in the sum-of-norms clustering model, and let the threshold separating the regime where SON clustering fails to separate…

Let SCORE denote the community-detection procedure whose clustering step is $k$-means, and let the NSP be the clustering property established for SCORE by Theorem … , and hence the…

Let $\bm{x}^*(\lambda)=[\bm{x}_1^*(\lambda),\ldots,\bm{x}_n^*(\lambda)]\in\bm{\mathrm{R}}^{nd}$, for $\lambda\in[0,\infty)$, be a trajectory of optimizers to a weighted formulation…