Information flows and Information bottlenecks in Network Coding

Transport of information is fundamentally different from transport of traditional commodities, since information can be copied and transformed during transmission while ordinary commodities cannot. The main challenge is to develop results and techniques for handling digital information. The main technical challenge and motivation is to use the insights and results in Network Coding to attack the matrix transposition problem as well as Valiant's shift problem which are both long standing open questions in circuit complexity theory.The purpose of the proposal is to investigate how information can most efficiently be transmitted through various types of communication networks. The project will use recent computer generated results in Information theory to identify and reason about information bottlenecks. The main motivation for the work is to understand information flows and information bottlenecks in a context that is relevant to long standing open questions in (Circuit) Complexity Theory. The project also aims at bridging the gab between these theoretical questions and potential applications of Network Coding.