@TechReport{Dartmouth:TR2005-548,
  author = {Marco D. Adelfio},
  title = {{Lower Bounds on the Communication Complexity of Shifting}},
  institution = {Dartmouth College, Computer Science},
  address = {Hanover, NH},
  number = {TR2005-548},
  year = {2005},
  month = {June},
  URL = {http://www.cs.dartmouth.edu/reports/TR2005-548.pdf},
  comment = {
    Senior Honors Thesis, 2005. Awarded High Honors.
  },
  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.
  }
}