Applications of Sheaf Cohomology and Exact Sequences to Network Coding (Frontiers in mathematical science through collaborations with other disciplines)
Robert Ghrist, Yasuaki Hiraoka · Kyoto University Research Information Repository (Kyoto University) · 2011
IntroductionThis paper introduces new tools for the analysis of data flows over networks.We focus on (linear) network coding [2,15], an important class of problems with numerous applications to error correction, optimal throughput, network security, and distribution [3].Network coding is one of a host of problems in data analysis and management that require an understanding of local-to-global transitions.The novel tools we present in this paper are based on sheaf theory [1,4,8,10].Sheaf theory was invented in the mid $1940s$ as a branch of algebraic topology to organize 10- cal strtlct $\iota$ ires on topological spaces [10, Introduction].Via its successes in several complex vari- ables and algebraic geometry, sheaves are now indispensable in modem mathematics.How- ever, despite its prowess in dealing with local-to-global transitions, sheaf theory has rarely if ever formd concrete applications to problems in science or engineering.The few exceptions in the literature (e.g., [5,14]) have dealt with applications to logic/semantics in Computer Science and use categorical properties of sheaves to organize local data.This paper introduces the following principal ideas:1. SHEAVES are an excellent tooI for organizing network information flows; 2. SHEAF COHOMOLOGY yields global characterizations of networks with coding; EXACT SEQUENCES allow for easy manipulation and computation of the above.