Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR15-167 | 15th October 2015 06:51

#### A Composition Theorem for Conical Juntas

TR15-167
Authors: Mika Göös, T.S. Jayram
Publication: 18th October 2015 01:17
Keywords:

Abstract:

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two applications:

$\bullet~$ $\textbf{AND-OR trees}$: We show a near-optimal $\tilde{\Omega}(n^{0.753...})$ randomised communication lower bound for the recursive NAND function (a.k.a. AND-OR tree).

$\bullet~$ $\textbf{Majority trees}$: We show an $\Omega(2.59^k)$ randomised communication lower bound for the 3-majority tree of height $k$. This improves over the state-of-the-art already in the context of randomised decision tree complexity.

ISSN 1433-8092 | Imprint