87 problems

Let $k$ be the target rank, let $d$ be the sketching dimension, and let $?\zeta$ denote the sparsity of a SparseStack matrix, a structured random matrix used as a dimensionality-re…

Diaconis's mixing-time conjecture. The mixing time of the torus shuffle is

Random-initialization convergence conjecture. When $m\geq Cn$, for $C>0$ large enough, alternating projections converge to the true solution with probability at least $1-\epsilon$.

Let $S$ be the limiting distribution of the search cost associated to a sequence $\omega$ of independent and identically distributed positive random variables. Let $S_1$ be a rando…

Let $I(n,p)$ be the number of inversions produced by unreliable Quicksort on $n$ items when each comparison is erroneous with probability $p$. Assume that $(np)^{-1}\sim\log n$, an…

Let $I(n,p)$ be the number of inversions produced by unreliable Quicksort on $n$ items when each comparison is erroneous with probability $p$, and let $U$ denote the random variabl…

Barvinok's asymptotic exactness conjecture. There exist a sequence $\{\gamma_d\}$ of non-negative real numbers and, for every $d$ and $\epsilon>0$, a sequence of functions…

Consider the volume problem of approximating the volume of a convex body using the oracle model studied in the source. Volume complexity conjecture. Although the best known algorit…

Yao–Karp conjecture. The same lower bound holds for randomized decision tree complexity:

Let $D(f)$ denote the deterministic decision tree complexity of a Boolean function $f$, and let $R(f)$ denote its randomized decision tree complexity. Define … For the recursively…

Let $(a_0,a_1,\dots,a_l)$ be a sequence generated by the CCL procedure, and let $\pi$ be the fast forward permutation coded by this sequence. Choose $x\in\{0,\dots,N-1\}$ uniformly…

Let $f$ be an $L$-smooth function. A Goldstein approximate second-order stationary point (SOSP) is an approximate second-order stationary point in the Goldstein sense, as defined i…

The randomized Exponential Time Hypothesis (rETH) is the hypothesis that $3$-SAT has no randomized algorithm with running time subexponential in the number of variables and success…

Let the inverse participation ratio (IPR) measure the concentration of the residual, and consider power-weighted sampling in an asynchronous randomized Jacobi method. Dual-role con…

Bounded relaxation-levels conjecture. We conjecture that $L$ is bounded independently of $n$, the number of vertices in the input graph. This would yield a linear-time parallelizab…

An acknowledgement-based contention-resolution protocol is a protocol in which a message's waiting time may be chosen from a non-geometric distribution depending on its collision c…

Consider a multiple-access channel in discrete time with Poisson arrivals of mean birth rate $\lambda>0$. A backoff protocol is specified by a send sequence…

GlobalClock contention-resolution conjecture. In the finite setting, there exists a protocol with latency $O(n)$ with high probability against an adaptive adversary. In the unbound…

Let $RP$ be the class of algorithmic problems solvable in polynomial time using randomness, and let $P$ be the class of algorithmic problems solvable in polynomial time by a determ…

Let a system have size $m \times n$, and let a coreset be a subset or compressed representation of the system used to retain the relevant approximation or solution properties. Line…

Mindegree-1 tightness conjecture. Maker has a randomized strategy to win with probability at least

The experiments compare theoretical relative errors with empirical relative errors obtained by repeating the algorithm ten times for each sample size. When the sample size is small…

Let $A^{(t)}$ denote the matrix produced after $t$ steps of the uniformly random pivoting procedure, and let $A$ be the initial matrix. Write $kappa(A)$ for the condition number of…

Let $\varphi$ be a [?]

Alekhnovich–Ben-Sasson conjecture. The terminator threshold matches the satisfiability threshold: