Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-111 | 16th November 2020 07:13

Lifting with Sunflowers

RSS-Feed




Revision #1
Authors: Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang
Accepted on: 16th November 2020 07:13
Downloads: 736
Keywords: 


Abstract:

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). Whereas previous proofs used sophisticated Fourier analytic techniques, our proof uses elementary counting together with a novel connection to the sunflower lemma.

In addition to a simplified proof, our approach also gives quantitative improvements in terms of \emph{gadget size}. 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 \emph{robust sunflower lemmas} allows us to reduce the gadget size to near linear. We conjecture that it can be further improved to poly logarithmic, similar to the known bounds for the corresponding robust sunflower lemmas.



Changes to previous version:

"Lifting: As Easy as 1,2,3" (TR20-111) and "Improved lifting theorems via robust sunflowers" (TR20-048) merged.


Paper:

TR20-111 | 24th July 2020 22:53

Lifting: As Easy As 1,2,3





TR20-111
Authors: Ian Mertz, Toniann Pitassi
Publication: 25th July 2020 08:05
Downloads: 958
Keywords: 


Abstract:

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). Whereas previous proofs used sophisticated Fourier analytic techniques, our proof uses elementary counting together with the sunflower lemma.



ISSN 1433-8092 | Imprint