64 problems

Determine whether there exist universal constants $C,c>0$ and a polynomial-time online signing algorithm such that, for every dimension $n\ge 1$ and every finite horizon $T$, when…

The subunit-$L^p$ discrepancy conjecture. For every dimension $d\geq2$ and every $0<p<1$, there is a constant depending only on $d$ and $p$ such that

Fix an integer $B\geq2$, and let $\mathcal{C}_B$ be the set of irrational numbers whose partial quotients are bounded in average by $B$. For each $n$, consider rational points…

Let $p$ be prime, let $\psi_k$ be the arithmetic permutation considered in the paper, and let $D(\psi_k)$ denote its discrepancy. Strong logarithmic discrepancy conjecture. … This…

Let $p$) be prime, let $\mathbb{Z}_p^\times$ denote the nonzero residue classes modulo $p$, and let $\psi_k$ be the arithmetic permutation defined in the surrounding discussion. Wr…

Let $\mathcal{S}=(\mathcal{I}_1,\mathcal{I}_2,\dots)$ be an infinite-length strategy, and define … Here $\operatorname{disc}(n)$ is the optimal discrepancy for finite strategies of…

For each positive integer $n$, let $\operatorname{disc}(n)$ be the minimum, over all strategies of length $n$ that repeatedly split an existing interval into two starting from…

Let $n\geq 1$ be an integer, and let $a_1,\ldots,a_n\in\mathbb{C}^n$ satisfy … A complex number of modulus $1$ is unimodular, and a vector in $\mathbb{C}^n$ is a unimodular vector…

Let $\mathcal H$ be a hypergraph on a finite ground set $X$, where every vertex has degree at most $d$. Beck–Fiala's conjecture. There exists a function $f:X\rightarrow\{-1,1\}$ su…

Optimal expected online discrepancy conjecture. For all $2\leq d\leq n/2$,

Let $B_2^d$ denote the Euclidean unit ball in $\mathbb{R}^d$, and let $S(B_2^d)$ be its Steinitz constant: the smallest $C$ such that every finite set of vectors $V\subset B_2^d$ w…

Let $H_k$ be the $2^k\times2^k$ Hadamard matrix obtained by the Sylvester construction, so $H_0=1$ and $H_k=H_1\otimes H_{k-1}$. For $x\in\\{\pm1\\}^{2^k}$, define…

Spencer discrepancy lower-bound conjecture. The infinite-family normalized discrepancy satisfies

K51mlf3s conjecture. There exists a universal constant $K$ such that every square matrix $A$ whose columns have unit $\ell_2$ norm satisfies

Let $\mathbb{S}^{(d-1)}$ be the sphere and let $\Delta:\mathbb{S}^{(d-1)}\to [0,1]$ denote the spherical cap discrepancy. Global Lipschitz continuity conjecture. The spherical cap…

Let $\mathscr L_k$ denote the space of lattices of the form $A\mathbb Z^k$ with $A \in \mathrm{SL}_k(\mathbb R)$, and let $k \geqslant 3$. Let $f$ be the product of the linear form…

Discrepancy-order conjecture. For $m e 0$,

Complete quasi-equidistribution claim. The Hammersley point set in base $$ is completely quasi-equidistributed in base $2$.

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 $\bm A_1,\dots,\bm A_T\in\mathbb{R}^{n\times n}_{\operatorname{sym}}$ be i.i.d. random symmetric matrices, where $T=T(n)$, $\|\bm A_i\|\leq1$ almost surely, the distribution is…

Let $K\subseteq\mathbb{R}^d$ be a zonotope. For symmetric convex bodies, the vector balancing constant $\operatorname{vb}(K,K)$ is the least $r\geq0$ such that every finite sequenc…

Let $T$ be a positive integer, let $v_1,\ldots,v_T\in\mathbb{B}_2^d$ be adversarial input vectors, and let $[T]=\{1,\ldots,T\}$. A signing is a vector $x\in\{\pm1\}^T$. Strong Koml…

General resolution-proof certificate conjecture. For any unsatisfiable formula $F$ and resolution proof $T$, the resulting vector $\bm\mu$ satisfies

Let $d\geq 1$ be an integer, and let $\mathbf{N}=(N_1,N_2,\cdots,N_d)$, where $N_1,\dots,N_d$ are positive integers. Write $\mathcal{A}_{\mathbf{N}}$ for the family of arithmetic p…

Let $v_1,\ldots,v_T\in\mathbb{R}^m$ be a sequence of vectors with Euclidean norm at most $1$. In the oblivious adversarial online setting, the algorithm receives $v_t$ at time $t$…