Appears in collection : Nexus Trimester - 2016 - Central Workshop

The capacity of a point-to-point communication channel under a zero-error criterion was originally studied by Shannon in 1956. Despite the apparent simplicity of the problem, and in contrast to its epsilon-error counterpart, a full characterization of the zero-error capacity remains elusive even for very simple channel models. Nevertheless, its study has had a significant influence on graph theory, and has led to some fascinating relations, constructions, and techniques. In this talk, I will briefly survey a few of the basic elements in this field, and then describe some recent work on the more general question of multiuser zero-error capacity in simple broadcast and multiple access models.