文章基本信息

标题：Lifting: As Easy As 1,2,3
本地全文：下载
作者：Ian Mertz ; Toniann Pitassi
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-25
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.