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

A large body of work studies the complexity of selecting the
$j$-th largest element in an arbitrary set of $n$ elements (a.k.a.
the select$(j)$ operation). In this work, we study the
complexity of select in data that is partially structured by
an initial preprocessing stage and in a data structure ... more >>>