Dartmouth College Computer Science
Technical Report series
TR search TR listserv
|By author:||A B C D E F G H I J K L M N O P Q R S T U V W X Y Z|
|By number:||2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986|
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
Senior Honors Thesis, 2005. Awarded High Honors.
Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]
Or copy and paste:
Marco D. Adelfio, "Lower Bounds on the Communication Complexity of Shifting." Dartmouth Computer Science Technical Report TR2005-548, June 2005.
Notify me about new tech reports.
Search the technical reports.
To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu
Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Technical reports collection maintained by David Kotz.