The work of Rothblum, Vadhan, and Wigderson ({\em STOC}, 2013) is pivotal to the study of interactive proofs of proximity (IPPs).
We present the main contents of their work, while clarify a few (conceptual) aspects.
Specifically, starting with the definition of IPP systems, our main focus is on ... more >>>

In this work, we study the space complexity of sketching the intersection profile of a distribution $D$ on $2^{[n]}$. Specifically, we seek a succinct data structure that, for any query set $S \subseteq [n]$, approximates the quantity $\Pr_{T \sim D}[T \cap S \neq \emptyset]$ to within a small constant additive ... more >>>

Let $S\subseteq {\mathbb F}_2^u$ have size $n=2^\ell$, and let $h:{\mathbb F}_2^u\to {\mathbb F}_2^\ell$ be a uniformly random linear map. For
$y\in{\mathbb F}_2^\ell$, write ${load}_h(y):=|h^{-1}(y)\cap S|$, and let
$M(S,h):=\max_{y\in{\mathbb F}_2^\ell}\{load}_h(y)$ be the maximum load. Jaber, Kumar and Zuckerman (STOC 2025) proved that the expected maximum load of $h$ on $S$ is ... more >>>