Event calendar file
School of Technology and Computer Science Seminars
On Shannon's Zero Error Capacity of a Graph
by Gowtham Raghunath Kurri (School of Technology and Computer Science, TIFR)
Friday, September 1, 2017
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
| Description |
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. |
