Tata Institute of Fundamental Research
On Shannon's Zero Error Capacity of a Graph
STCS Student Seminar
Speaker:
Gowtham Raghunath Kurri
Organiser:
Aditya Nema
Date:
Friday, 1 Sep 2017, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Suppose we want to transmit messages across a noisy channel to a receiver. The maximum rate of transmission such that the receiver may recover the original message without errors (i.e., zero error) is called zero error capacity of the channel. In this context, a channel can be represented by a graph and Shannon(1956) computed the capacity of all graphs with five or fewer vertices - with the single exception of C_5 (a cycle with 5 vertices). Later, Laszlo Lovasz (1979) solved this seemingly very difficult combinatorial problem by showing that capacity of C_5 is \sqrt(5) with an astonishingly simple argument. In this talk, we will first develop the required background and discuss his proof.
| Speaker: | Gowtham Raghunath Kurri |
| Organiser: | Aditya Nema |
| Date: | Friday, 1 Sep 2017, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Suppose we want to transmit messages across a noisy channel to a receiver. The maximum rate of transmission such that the receiver may recover the original message without errors (i.e., zero error) is called zero error capacity of the channel. In this context, a channel can be represented by a graph and Shannon(1956) computed the capacity of all graphs with five or fewer vertices - with the single exception of C_5 (a cycle with 5 vertices). Later, Laszlo Lovasz (1979) solved this seemingly very difficult combinatorial problem by showing that capacity of C_5 is \sqrt(5) with an astonishingly simple argument. In this talk, we will first develop the required background and discuss his proof.