hide
Free keywords:
-
Abstract:
Let f be a Boolean function of $n$ variables with $L_1$ spectral norm
$ L_1(f)>n^\epsilon $ for some positive $ \epsilon $ . Then f can be computed
by a
$ O(\log L_1(f)) $ player multi--party protocol with $ O(\log^2 L_1(f)) $
communication.