Algebra & Geometry Seminar, Linear Network Coding over Ring Alphabets; Speaker: Joseph Connelly, Air Force Research Labs

Event Type: 
Joseph Connelly, Air Force Research Labs
Event Date: 
Wednesday, August 29, 2018 -
3:00pm to 3:45pm
SMLC 352
Dimiter Vassilev

Event Description: 

Abstract:  In a network, senders and receivers are connected via a series of intermediate users who share information represented as elements of some finite alphabet. By allowing users to transmit functions of their inputs, as opposed to simply relaying received data, the information throughput of a network can be increased. Network codes in which these functions are linear are suboptimal in general but are of practical interest due to their tractability and implementation complexity. The study of linear network coding has primarily been limited to finite field alphabets.  In this talk, we discuss linear network codes over more general algebraically-structured alphabets, namely finite rings. We contrast linear network codes over finite fields, commutative rings, and non-commutative rings.  In particular, we show that fixed-size commutative rings are quasi-ordered such that higher-ordered rings are, in a certain sense, “better” for linear network coding, and we characterize the commutative rings that are maximal with respect to this quasi-order.  We prove that: (i) each finite field is such a maximal ring, and (ii) there is a unique maximal commutative ring of size m if and only if each prime factor of m has multiplicity in {1,2,3,4,6}.  We also present networks for which certain non-commutative rings can attain linear coding solutions when no commutative ring can. Finally, we show that vector linear codes, wherein the alphabet is the set of all vectors over a field, minimize the alphabet size needed for a linear solution, even when very general linearity is allowed.


More Information:


(They are also available


Bio:  Joseph received Bachelor's degrees in electrical and computer engineering from the University of Minnesota Twin Cities in 2013.  He received the M.S. and Ph.D. degrees in electrical engineering (communication theory & systems) from the University of California, San Diego in 2016 and 2018, respectively.  In 2016, he was with the NASA Jet Propulsion Laboratory, and he is currently with the Air Force Research Labs in Albuquerque, New Mexico.  Dr. Connelly was the recipient of the UCSD Shannon Memorial Fellowship in 2016, and he received the UCSD ECE Department Best Thesis Award in 2018.


Event Contact

Contact Email: