User Tools

Site Tools


seminars:comb:abstract.201010bow

Garry Bowlin (Binghamton)

Linear Programming Decoding and Signed Graphs

Abstract for the Combinatorics Seminar 2010 October 12

The problem of exact maximum-likelihood decoding of general linear codes is well-known to be NP-hard. If we do not require our algorithm to always give us a codeword it is possible to develop a decoder using linear programming. In the particular case of the cycle code of a graph G, we can even understand the non-codeword outputs of the linear programming decoder. These pseudo-codewords are the vector representations of cycles in the all-negative signed graph -G.


seminars/comb/abstract.201010bow.txt · Last modified: 2020/01/29 14:03 (external edit)