We present a simple method based on a variant of Hölder's inequality to lower-bound the trace norm of Boolean matrices. As the main result, we obtain an exponential separation between the randomized decision tree depth and the spectral norm (i.e. the Fourier $L_1$-norm) of a Boolean function. This answers an ... more >>>

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions. They showed that under a very strong complexity theoretic hardness assumption, there are extractors for samplable distributions with large min-entropy of $k=(1-\gamma) \cdot n$, for some small constant $\gamma>0$. Recent work by Ball, Goldin, Dachman-Soled and ... more >>>

Direct sum theorems state that the cost of solving $k$ instances of a problem is at least $\Omega(k)$ times
the cost of solving a single instance. We prove the first such results in the randomised parity
decision tree model. We show that a direct sum theorem holds whenever (1) the ... more >>>