Two fundamental problems on directed graphs are to decide $s$-$t$ connectivity, and to estimate the behavior of random walks. Currently, there is no known algorithm for $s$-$t$ connectivity running in polynomial time and $n^{o(1)}$ space, and no known algorithm for estimating the $n$-step random walk matrix running in non-deterministic logspace. ... more >>>

We investigate the sample complexity of mutual information and conditional mutual information testing. For conditional mutual information testing, given access to independent samples of a triple of random variables $(A, B, C)$ with unknown distribution, we want to distinguish between two cases: (i) $A$ and $C$ are conditionally independent, i.e., ... more >>>

Given a sequence of $N$ independent sources $\mathbf{X}_1,\mathbf{X}_2,\dots,\mathbf{X}_N\sim\{0,1\}^n$, how many of them must be good (i.e., contain some min-entropy) in order to extract a uniformly random string? This question was first raised by Chattopadhyay, Goodman, Goyal and Li (STOC '20), motivated by applications in cryptography, distributed computing, and the unreliable ... more >>>