Synchronizing rankings via interactive communication

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the novel problem of exact synchronization of two rankings at remote locations connected by a two-way channel. Such synchronization problems arise when items in the data are distinguishable, as is the case for playlists, tasklists, crowdvotes and recommender systems rankings. Our model includes different constraints on the communication throughput of the forward and feedback links, resulting in different anchoring, syndrome and checksum computation strategies. Information editing is assumed of the form of deletions, insertions, block deletions/insertions, translocations and transpositions. The protocols developed under the given model are order-optimal with respect to genie aided lower bounds.

Original languageEnglish (US)
Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Print)9781479951864
StatePublished - 2014
Event2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States
Duration: Jun 29 2014Jul 4 2014

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Other2014 IEEE International Symposium on Information Theory, ISIT 2014
Country/TerritoryUnited States
CityHonolulu, HI

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Synchronizing rankings via interactive communication'. Together they form a unique fingerprint.

Cite this