Complexity of Sampling and Communication

The unifying topic of this thesis is the relation of randomness to computation. We study two different facets of this: the hardness of sampling from probability distributions and the extent of usefulness of randomness in communication complexity.

Hardness of Sampling. A circuit samples the distribution of its output on a uniformly random input. What distributions are samplable with small circuits? What about local circuits (NC0)? We make two contributions in this direction. The first is to show that sampling uniformly from the set of Hamming-weight-k n-bit string is hard for NC0-circuits (and even constant-width DNFs) as long as k=o(n). The second is to show that sampling a uniformly random permutation of [n] elements requires polylog(n) adaptive queries to a sequence of uniform input symbols from [n]---adaptive cell probes. These results refine our understanding of sampling by constant-depth de Morgan circuits (AC0).

Randomness in Communication. The classical example separating deterministic and randomized communication is the Equality problem: Alice and Bob are to decide whether their n-bit inputs are equal. It requires transmitting n+1 in the deterministic model, but is solvable with a constant-cost protocol using public randomness. An active line of research found many non-trivial problems that are solvable with just constant-cost randomized communication [Harms-Wild-Zamaraev, STOC 2022; Hambardzumyan-Hatami-Hatami, Isr. J. Math.; Fang-Hambardzumyan-Harms-Hatami, STOC 2024; Fang-Göös-Harms-Hatami, STOC 2025]. All of those problems can be solved with polylog(n) queries to Equality oracle. Our first contribution is to exhibit a problem that is solvable with constant-cost randomized communication, but requires polynomially many calls to Equality oracle. This resolves an open problem in the survey [Hatami-Hatami, ACM SIGACT News].

Our second contribution is to investigate when the randomized communication complexity can be localized or condensed: for a matrix of randomized communication cost k, can we find its 2^k-by-2^k submatrix that retains communication cost at least linear in k$? In general this is impossible [Hambardzumyan-Hatami-Hatami, Discrete Appl. Math.]. We show, however, that in an important case it can be done: we condense randomized communication cost of sink-of-xor function---a recent counterexample to log-approximate-rank conjecture by [Chattopadhyay-Mande-Sherif, J. ACM], and thereby quantitatively improve the counterexample.