Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-048 | 16th April 2020 19:59

Improved lifting theorems via robust sunflowers


Authors: Shachar Lovett, Raghu Meka, Jiapeng Zhang
Publication: 16th April 2020 20:49
Downloads: 1009


Lifting theorems are a generic way to lift lower bounds in query complexity to lower bounds in communication complexity, with applications in diverse areas, such as combinatorial optimization, proof complexity, game theory. Lifting theorems rely on a gadget, where smaller gadgets give stronger lower bounds. However, existing proof techniques are known to require somewhat large gadgets.

We focus on one of the most widely used gadgets, the index gadget. For this gadget, existing lifting techniques are known to require at least a quadratic gadget size. We develop a new approach to prove lifting theorems for the indexing gadget, based on a novel connection to the recently developed robust sunflower lemmas. We show that this allows to reduce the gadget size to linear. We conjecture that it can be further improved to poly logarithmic, similar to the known bounds for the corresponding robust sunflower lemmas.

ISSN 1433-8092 | Imprint