Paper Info
Title
Exponentially Simpler Network Rate Regions
Abstract
Determining the rate region of a network is of great importance in the research area of network coding. Lots of attempts have been made and significant progress has been achieved over the last decade on this topic. Although these researches provide us with multiple ways of calculating the outer or inner bounds of rate region, the sheer complexity of the problem, which involves expressing and projecting a very high dimensional polyhedra, makes it computationally infeasible beyond networks with IOs of edges.Aimed at reducing the complexity of the rate region calculation, in this paper a new theorem that implicitly determines the rate region of a network is proved and a corresponding systematic way of applying the theorem to calculate explicitly the outer bounds to a rate region is proposed. Compared with the traditional method, the proposed method has the potential to calculate the true rate region via the projection of simpler polyhedra that has exponentially less dimensions and is characterized by exponentially less facets.
Year
DOI
Venue
2021
10.1109/ISIT45174.2021.9517734
2021 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT)
Keywords
DocType
Citations 
network coding cuts, rate regions, complexity reduction
Conference
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Yirui Liu100.68
John MacLaren Walsh210717.90