Shengyu Zhang

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

    Authors: Rahul Jain, Hartmut Klauck, Shengyu Zhang
    Subjects: Computational Complexity
    Abstract

    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 results complement the recent
    lower bound of $\Omega(n/8^d)$ by Leonardos and Saks and
    $\Omega(n/2^{\Omega(d\log d)})$ by Jayram, Kopparty and Raghavendra for
    randomized communication complexity of read-once Boolean formulas with depth
    $d$. We obtain our result by "embedding" either the Disjointness problem or its
    complement in any given read-once Boolean formula.

Syndicate content