Note:My apologies to anyone forced to miss this seminar because they are protesting in Boston. I'm afraid we've lost too many seminar sessions this term for me to reschedule another one -- DAMB.
Many recent and emerging network technologies offer substantially more bandwidth in one direction than the other. Adler and Maggs introduced a communication model for this scenario and show that a high-speed link from server to client can be used to greatly reduce the number of bits sent across the slower client to server link.
The model features a client sending an n-bit string to a server over
an asymmetric channel, with only the server able to access the
distribution D from which the client's string is drawn. Adler and
Maggs present several protocols in which the number of server and
client bits are, respectively, O(n) and O(H(D)+1), where H(D) is
the binary entropy of the distribution D.
I will present the communication model and a new variant of the
protocol Round-efficient from the Adler and Maggs paper. Like
Round-efficient, our protocol is existentially optimal. The new work
reduces the computational requirements of Round-efficient from
O(2n) to O(n2^H(D)).
Last modified 25 April 2003