License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2016.5
URN: urn:nbn:de:0030-drops-58497
Go to the corresponding LIPIcs Volume Portal

Göös, Mika ; Jayram, T. S.

A Composition Theorem for Conical Juntas

28.pdf (0.6 MB)


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.

BibTeX - Entry

  author =	{Mika G{\"o}{\"o}s and T. S. Jayram},
  title =	{{A Composition Theorem for Conical Juntas}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Ran Raz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-58497},
  doi =		{10.4230/LIPIcs.CCC.2016.5},
  annote =	{Keywords: Composition theorems, conical juntas}

Keywords: Composition theorems, conical juntas
Collection: 31st Conference on Computational Complexity (CCC 2016)
Issue Date: 2016
Date of publication: 19.05.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI