We examine the communication required for generating random variables remotely. One party Alice will be given a distribution D, and she has to send a message to Bob, who is then required to generate a value with distribution exactly D. Alice and Bob are allowed to share random bits generated ... more >>>

The best-known representations of boolean functions f are those of disjunctions of terms (DNFs) and as conjuctions of clauses (CNFs). It is convenient to define the DNF size of f as the minimal number of terms in a DNF representing f and the CNF size as the minimal number of ... more >>>

We study the complexity of computing Boolean functions using AND, OR and NOT gates. We show that a circuit of depth $d$ with $S$ gates can be made to output a constant by setting $O(S^{1-\epsilon(d)})$ (where $\epsilon(d) = 4^{-d}$) of its input values. This implies a superlinear size lower bound ... more >>>