Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas

Rahul Jain, Hartmut Klauck, Shengyu Zhang

We show lower bounds of $\Omega (\sqrt{n})$ and $\Omega (n^{1/4})$ on the randomized and quantum communication complexity, respectively, of all $n$-variable read-once Boolean formulas. Our res…