Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-111 | 24th July 2020 22:53

Lifting: As Easy As 1,2,3

RSS-Feed




TR20-111
Authors: Ian Mertz, Toniann Pitassi
Publication: 25th July 2020 08:05
Downloads: 413
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