Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-167 | 15th October 2015 06:51

A Composition Theorem for Conical Juntas

RSS-Feed




TR15-167
Authors: Mika Göös, T.S. Jayram
Publication: 18th October 2015 01:17
Downloads: 2613
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