BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR2005-548
ENTRY:: October 20, 2005
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Lower Bounds on the Communication Complexity of Shifting
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Adelfio, Marco D.
DATE:: June 2005
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR2005-548.pdf
ABSTRACT:: 
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.
NOTE:: 
Senior Honors Thesis, 2005. Awarded High Honors.
END:: ncstrl.dartmouthcs//TR2005-548