4 problems

Let $p_1,p_2,\dots$ be a sequence of arbitrary discrete distributions presented adaptively over time. An online random sampling algorithm generates exact samples from these distrib…

Let $d\geq 1$ and let $\varepsilon>0$. Consider online random sampling algorithms that, for every sequence of distributions on a $d$-element alphabet, generate independent samples…

Let $\{F_n\}_{n=1}^{\infty}$ be families of $k$-CNF formulas of size $\Theta(n)$. The total space of a resolution refutation of $F_n$ is denoted by $\operatorname{TotSp}(F_n)$. Ale…

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…