%T Lower Bounds on the Communication Complexity of Shifting
%A Marco D. Adelfio
%R Technical Report TR2005-548
%I Dartmouth College, Computer Science
%C Hanover, NH
%D June 2005
%U http://www.cs.dartmouth.edu/reports/TR2005-548.pdf
%X
 We study the communication complexity of the SHIFT (equivalently,
 SUM-INDEX) function in a 3-party simultaneous message model.  Alice and
 Bob share an n-bit string x and Alice holds an index i and Bob an index
 j. They must send messages to a referee who knows only n, i and j,
 enabling him to determine x[(i+j) mod n].  Surprisingly, it is possible
 to achieve nontrivial savings even with such a strong restriction: Bob
 can now make do with only ceil(n/2) bits.  Here we show that this bound
 is completely tight, for all n. This is an exact lower bound, with no
 asymptotics involved.
%Z
 Senior Honors Thesis, 2005. Awarded High Honors.