ECCC-Report TR01-019https://eccc.weizmann.ac.il/report/2001/019Comments and Revisions published for TR01-019en-usMon, 05 Mar 2001 14:15:00 +0200
Paper TR01-019
| The Communication Complexity of Enumeration, Elimination, and Selection |
Andris Ambainis,
Harry Buhrman,
William Gasarch,
Bala Kalyansundaram,
Leen Torenvliet
https://eccc.weizmann.ac.il/report/2001/019Normally, 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.
Mon, 05 Mar 2001 14:15:00 +0200https://eccc.weizmann.ac.il/report/2001/019