In this paper, we construct pseudorandom generators for the class of \emph{combinatorial sums}, a class of functions first studied by \cite{GMRZ13}
and defined as follows: A function $f: [m]^n \rightarrow \{0,1\}$ is said to be a combinatorial sum if there exists functions $f_1, \ldots, f_n: [m] \rightarrow \{0,1\}$ such that
more >>>

We propose the following computational assumption: in general if we try to compress the depth of a circuit family (parallel time) more than a constant factor we will suffer super-quasi-polynomial blowup in the size (number of processors). This assumption is only slightly stronger than the popular assumption about the robustness ... more >>>

The noisy population recovery problem is a basic statistical inference problem. Given an unknown distribution in $\{0,1\}^n$ with support of size $k$,
and given access only to noisy samples from it, where each bit is flipped independently with probability $1/2-\eps$,
estimate the original probability up to an additive error of ... more >>>