2026-08-10T20:05:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5849 2024-03-06T10:37:08Z ddc:004 open_access

A Composition Theorem for Conical Juntas Göös, Mika Jayram, T. S. Composition theorems conical juntas 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mika Göös and T. S. Jayram 2016 Is Part Of LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2016.5 urn:nbn:de:0030-drops-58497 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.5 eng https://creativecommons.org/licenses/by/3.0/legalcode