Lower Bound for the Communication Complexity of the Russian Cards Problem

Details Lower Bound for the Communication Complexity of the Russian Cards Problem Lower Bound for the Communication Complexity of the Russian Cards Problem

2008-05-14

arxiv.org/abs/0805.1974v2

Computer Science

Logic in Computer Science

5 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Lower Bound for the Communication Complexity of the Russian Cards Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lower Bound for the Communication Complexity of the Russian Cards Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bound for the Communication Complexity of the Russian Cards Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-55354