18 problems

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

Let $G$ be the graph in the paper's online model, let $\mathcal{A}(G)$ be the set selected by an online algorithm $\mathcal{A}$, and let $E$ be the set of all future edges ever rev…

Let $G_{\mathrm{bip}}(n,p)$ be the random bipartite graph in the online model considered in the source, let $\gamma$ be the balance parameter, and let $\alpha_{\rm COMP}$ denote th…

Constant-playability relaxation. Let $G=(V,E)$ be a graph without isolated edges. Then there exists a constant $c\in\mathbb{N}\cup\{0\}$ such that $G$ is $f$-unbalanceable, where

St. Ives matching conjecture. For all $k\geq 1$, there is a constant $c_k$ such that for all $n\geq 1$,

Let a $(t,b)$-strategy $B$ of Builder be a strategy that observes at most $t$ arriving edges and purchases at most $b$ of them. A graph is Hamiltonian if it contains a Hamilton cyc…

Let $k$ be a positive integer, let $\varepsilon>0$, and let a $(t,b)$-strategy $B$ of Builder be a strategy that observes at most $t$ arriving edges and purchases at most $b$ of th…

Kurek–Ruciński conjecture.

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$…

Let $d4a6$ denote the family of convex sets in $d53d^d$, let $d4a6^*$ be the set of finite strings with alphabet $d4a6$, and let an online selector be a map $S:d4a6^*\tod53d^d$ sat…

Let $d\in\mathbb{N}$ and let $\beta\in(0,1]$. A greedy-Haar $(1+\beta)$-thinning strategy produces a sequence $Z=(Z_n)_{n\geq 1}$, and write $Z^n=(Z_1,\ldots,Z_n)$ for its first…

Let ${\mathcal{A}}$ be an online binary search tree algorithm. Starting with any initial tree $T$ with $n$ elements, let $X$ be the preorder sequence of a binary search tree $T'$ t…

Let ${\mathcal{A}}$ be an online binary search tree algorithm. Starting with any initial tree $T$ with $n$ elements, consider any sequence of $n$ splits. A split at an element $x$…

Let ${\mathcal{A}}$ be an online binary search tree algorithm. Starting with any initial tree $T$ with $n$ elements, consider inserting or deleting the current minimum or maximum e…

Let $G$ be a graph and let $k\in\mathbb{N}$. The on-line chromatic number conjecture. Deciding whether … is textsc{PSPACE}-complete. The complexity of deciding whether the on-line…

On-line ranking conjecture. There exist universal constants $a$ and $b$ satisfying $0<a<1<b$ such that

Let $p$ be fixed in $(0,1)$, let $w(\lambda)$ denote the size of the lookahead window, and let $C^*_{\Pi_{w(\lambda)}}(p,\lambda)$ be the best achievable delay under policies…

Let $G$ be a graph, with vertex number $|V(G)|$, chromatic number $c7(G)$, and on-line choice number ${\rm ch}^{\rm OL}(G)$. A graph is on-line chromatic-choosable when…