## Tata Institute of Fundamental Research

### The Shannon Capacity of the 5-Cycle

##### Student Seminar
 Speaker: Rakesh Venkat Organiser: Shishir Pandey Date: Friday, 30 Nov 2012, 15:00 to 16:30 Venue: A-212 (STCS Seminar Room)

Abstract:  Imagine a secret agent in a terrorist camp who needs to get messages to the outside world. He has scarves of 5 colours $(A,B,C,D,E)$, and depending on the colour of the scarf he wears each day, an intelligence team who have satellite photography of the area decipher the message.
Unfortunately, the satellite system is not perfect and tends to mix up certain colours in it's images: $A$ may be confused with $E$ or $B$, $B$ with $A$ or $C$, and so on. The confusion graph forms a 5-cycle $A-B-C-D-E-A$. What protocol can the agent use to transmit his messages with the highest efficiency? (in terms of #messages per symbol).
For instance, if he uses just colours $A,C,$ then he transmits 1 bit every day and these are not confused. So he sends one of $2^k$ messages in $k$ days. But there is a better protocol that allows him to transfer one of $5^(k/2)$ messages in $k$ days.