文章基本信息

标题：The Communication Complexity of Enumeration, Elimination, and Selection
本地全文：下载
作者：Andris Ambainis ; Harry Buhrman ; William Gasarch 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Normally, communication Complexity deals with how many bits Alice and Bob need to exchange to compute f(x,y) (Alice has x, Bob has y). We look at what happens if Alice has x_1,x_2,...,x_n and Bob has y_1,...,y_n and they want to compute f(x_1,y_1)... f(x_n,y_n). THis seems hard. We look at various ways to approximate it. Our work is related to the Direct SUm Conjecture.
关键词：Communication complexity , Direct Sum Conjecture , Elimination , Enumeration , selection