Collection Nexus Trimester - 2016 - Fundamental Inequalities and Lower Bounds Theme
Organisateur(s)
Date(s)
19/05/2024
Composition Theorem for Conical Juntas with Applications to Query and Communication Complexity
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 Ω(n0. 753…)randomized communication lower bound for the recursive NAND function (a. k. a. AND-OR tree). This answers an open question posed by Beame and Lawry 1992,1993. Recursive Majority: We show an Ω(2. 59k)randomized 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.
