Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Bala Kalyansundaram:

TR01-019 | 2nd March 2001
Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

The Communication Complexity of Enumeration, Elimination, and Selection

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 ... more >>>

ISSN 1433-8092 | Imprint