非表示:
キーワード:
-
要旨:
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.
