文章基本信息

标题：A Composition Theorem for Conical Juntas
本地全文：下载
作者：Mika G{\"o}{\"o}s ; T. S. Jayram
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：50
页码：5:1-5:16
DOI：10.4230/LIPIcs.CCC.2016.5
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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: - AND-OR trees. We show a near-optimal ~Omega(n^{0.753...}) randomised communication lower bound for the recursive NAND function (a.k.a. AND-OR tree). This answers an open question posed by Beame and Lawry. - 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.
关键词：Composition theorems; conical juntas