10 problems

Let $F=F_n$ be a free group of rank $n$, and let $NMin_l\subset F$ be the set of all non-minimal elements of length $l$. Let $LR(w)$ denote the length-reducing complexity associate…

Low-degree conjecture. If there exist $\epsilon>0$ and $D=D(n)\geq (\log n)^{1+\epsilon}$ such that

Let ${\cal G}_{n,\delta}$ denote the Erdős–Rényi random graph model with edge probability $\delta$, and let $(K_n,\lambda)$ be a random simple temporal graph. A $\delta$-clique is…

In the $(k,N,r)$-SUM problem, the input consists of $r$ elements $z_1,\ldots,z_r$, independently and uniformly chosen from $\{-N,\ldots,N\}$. The goal is to find an ordered $k$-tup…

Fix constants $\gamma > 0$, $\beta > -1$, and $\rho \in (0,1)$. Let $N=N(n)$ satisfy $n/N \to \gamma$ as $n \to \infty$. In the spiked Wishart model, under $\mathbb{Q}$ the observa…

Let $\bW \in \mathbb{R}^{n \times n}_{\mathrm{sym}}$ be drawn from the Gaussian orthogonal ensemble, and let $\lambda^+(\bW)$ denote the non-negative principal component analysis o…

Let $\Omega$ be finite or $\mathbb R$, let $k$ be fixed, and let $N=\binom nk$. Let $\nu$ be a product distribution on $\Omega^N$, let $\mu$ be another distribution on $\Omega^N$,…

Let $m$ and $n$ be polynomial in one another. The problems $k\textsc{-pc}(n,k,1/2)$, $\textsc{bpc}(m,n,k_m,k_n,1/2)$, $k\textsc{-bpc}(m,n,k_m,k_n,1/2)$, and…

Let $\rho$ be a distribution on $k$-subsets of $[n]$, and let $p_\rho(s)=\mathbb P_{S,S'\sim\rho^{\otimes 2}}[|S\cap S'|=s]$ be the intersection-size probability mass function. Let…

Average-case hardness conjecture. (a) If