18 problems

Let $\Lambda_{1},\dotsc,\Lambda_{d}\in\mathbb{R}^{b\times b}$ be real diagonal matrices, and assume that $\Lambda_i$ and $\Lambda_j$ have disjoint spectra for $1\leq i<j\leq d$. Le…

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…

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…

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

Let $\varphi$ be a [?]

A 2-uniformity network is a network of lazy transpositions whose output permutation is uniformly distributed on every subset of two positions; let $U_2(n)$ denote the minimum lengt…

Aldous's conjecture. In the queue-free setting, no backoff protocol is stable for any positive value of $\lambda$.

Let $H=(V,E)$ be a hypergraph, let $w\in\mathbb{R}_{\geq 0}^E$ be edge weights, and let $x\in[0,1]^E$ be a fractional matching, meaning that … where $\delta(v)=\\{e\in E:v\in e\\}$…

Let $m=\Omega(n)$ balls be allocated to $n$ bins in the two-thinning setting, and let the overseer two-thin the allocations. More-balls conjecture. The asymptotically optimal maxim…

Let $n$ bins receive balls in the two-thinning setting, where the overseer may iteratively reject up to $k$ suggested allocations for each ball. More-choice conjecture. The asympto…

Let $K_n$ be the complete graph on $n$ vertices, and let $\Phi$ be the potential function on colorings of $E(K_n)$ with $n-1$ colors. Consider the process that starts from a random…

Let $[n]=\{1,\ldots,n\}$, let $\mathcal{U}(A)$ denote the uniform distribution on a finite set $A$, and let $(f,g)$ be probabilistic strategies satisfying the correctness condition…

Let $[n]=\{1,\ldots,n\}$, let $\bm{A}_1,\ldots,\bm{A}_n$ be positive semidefinite matrices, and let $k$ be a positive integer. For a function of an ordered $k$-tuple, define … and…

Let $r$ be a positive integer, let $C_{[0,t_1]}$ be a communication sequence, and let the $\mathrm{I\mathcal{V}SC}$ condition be the condition specified by the source. Let ARIS den…

Let $C_{[0,t_1]}$ be a communication sequence satisfying the $\mathrm{S\mathcal{V}SC}$ condition. Let the RIS algorithm be the algorithm proposed by Shah and Hassibi (2008), let th…

Let $C_{[0,t_1]}$ be a communication sequence, and let the $\mathrm{S\mathcal{V}CC}$ condition be defined by condition (C) of the cited theorem. Upon reception of each signal, choo…