In recent years, network coding has generated much interest in information theory, coding theory, networking, wireless communications, cryptography, and computer science. Consider a point-to-point communication network on which a number of information sources are to be multicast to certain sets of destination nodes. The problem is to characterize the maximum possible throughput. Contrary to one's intuition, network coding theory reveals that it is in general not optimal to regard the information to be transmitted as a "fluid" which can simply be routed or replicated. Rather, by employing coding at the nodes, bandwidth can in general be saved. In this talk, we will give an overview of network coding theory and its extensions for error correction and information security. We will also discuss various applications of network coding.

A fundamental problem in Cryptography is how to enable mutually distrustful entities to collaborate in a computational task without breaching the privacy of their data. We will present an elegant solution to this problem that ensures perfect privacy, provided that majority of the entities are honest (i.e., follows their prescribed instructions). As we show, this solution crucially relies on a tool, called Shamir's secret sharing, that is intimately connected with the Reed-Solomon codes.