Worst-case randomized interactive communication

TitleWorst-case randomized interactive communication
Publication TypeConference Paper
Year of Publication2005
AuthorsMercier, H., P. McKenzie, and S. Wolf
Conference NameInformation Theory, 2005. ISIT 2005. Proceedings. International Symposium on
Pagination430 -434
Date Publishedsep.
Keywordscommunication complexity, correlated data setting, correlation theory, direct-sum problem, private coin randomized model, public coin randomized model, random processes, randomized interactive communication

In the interactive communication model, two distant parties possess correlated inputs such as strings of bits, and the goal is for one party to learn his interlocutor's input while minimizing the communication. Our main contribution is to analyze the power of randomization in this correlated data setting. We show that the deterministic, amortized deterministic, private coin randomized, and public coin randomized models are all equivalent for a large class of problems arising from several practical applications. Furthermore, we conjecture that the private coin randomized model and the deterministic model are equivalent for every problem, and show that a proof of this statement solves the direct-sum problem for interactive communication


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia