2026-07-25T06:06:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15700 2024-03-06T10:55:59Z ddc:004 open_access

Lifting with Sunflowers Lovett, Shachar Meka, Raghu Mertz, Ian Pitassi, Toniann Zhang, Jiapeng Lifting theorems communication complexity combinatorics sunflowers Query-to-communication lifting theorems translate lower bounds on query complexity to lower bounds for the corresponding communication model. In this paper, we give a simplified proof of deterministic lifting (in both the tree-like and dag-like settings). Our proof uses elementary counting together with a novel connection to the sunflower lemma. In addition to a simplified proof, our approach opens up a new avenue of attack towards proving lifting theorems with improved gadget size - one of the main challenges in the area. Focusing on one of the most widely used gadgets - the index gadget - existing lifting techniques are known to require at least a quadratic gadget size. Our new approach combined with robust sunflower lemmas allows us to reduce the gadget size to near linear. We conjecture that it can be further improved to polylogarithmic, similar to the known bounds for the corresponding robust sunflower lemmas. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shachar Lovett and Raghu Meka and Ian Mertz and Toniann Pitassi and Jiapeng Zhang 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.104 urn:nbn:de:0030-drops-157004 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.104 eng https://creativecommons.org/licenses/by/4.0/legalcode