Lower Bound for the Communication Complexity of the Russian Cards Problem

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

In this paper it is shown that no public announcement scheme that can be modeled in Dynamic Epistemic Logic (DEL) can solve the Russian Cards Problem (RCP) in one announcement. Since DEL is a general model for any public announcement scheme we conclude that there exist no single announcement solution to the RCP. The proof demonstrates the utility of DEL in proving lower bounds for communication protocols. It is also shown that a general version of RCP has no two announcement solution when the adversary has sufficiently large number of cards.
5 pages

Keywords

Logic in Computer Science

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/213370

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0805.1974
 http://arxiv.org/abs/0805.1974

Collections

arXiv