9 problems

Fourier–Hahn–Lévy conjecture. If $f:\mathbb{Z}\to\mathbb{Z}$ is tractable, then the $f$-moment can be estimated to within a constant factor with a Lévy-Tower, either directly or af…

For a function $f$, its $f$-moment is the quantity … A function is tractable if its moment can be estimated to within a constant factor using a small sketch. Lévy–Khintchine repres…

For a function $f$ on the frequency domain, an $f$-moment is the quantity … A function is tractable if its moment can be estimated to within a constant factor using…

Let $\mathbf{x} \in \mathbb{R}_+^n$ be updated by an incremental stream. Let $G$ be a nonnegative function on the coordinates, and write…

Leighton–Samaniego's conjecture. The deterministic minimax risk is of this order:

Sample-complexity conjecture. The sample complexity of constant-space additive-$\epsilon$ entropy estimation is optimal up to factors polynomial in $\log(1/\epsilon)$; in particula…

Let $G$ be a finitely generated group that is not virtually nilpotent, and let its growth function count the elements representable by words of length at most $n$. Subexponential g…

Let a stream algorithm emulate a general utility-based pool algorithm, and suppose it is allowed a constant-factor increase in the number of element selections. Constant-factor imp…

Let $\text{\textsc{Dyck}}(2)$ denote the language of well-parenthesized expressions with two types of parentheses. Consider streaming algorithms that recognize length-$n$ instances…