Zobrazeno 1 - 3
of 3
pro vyhledávání: ''
Publikováno v:
FOCS
We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tilde{\Omega}(n/r + r)$ on the communication required for computing di
Autor:
Alexander A. Sherstov
Publikováno v:
FOCS
The threshold degree of a Boolean function $f$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv {sgn}~ p(x)$. Introduced in the seminal work of Minsky and Papert [Perceptrons: An Introduction to Computational Ge
Autor:
Benjamin Rossman
Publikováno v:
FOCS
We show that unbounded fan-in Boolean formulas of depth d + 1 and size s have average sensitivity $${O(\frac{1}{d} \log s)^d}$$ . In particular, this gives a tight $${2^{\Omega(d(n^{1/d}-1))}}$$ lower bound on the size of depth d + 1 formulas computi