Lunches‎ > ‎

Nov 24: Stopping sets in linear binary codes

posted Nov 21, 2014, 7:02 AM by Dirk Oliver Theis   [ updated Nov 21, 2014, 8:36 AM ]
For Monday, Nov 24, Yauhen Yakimenka (PhD student of Vitaly's) has promised to explain an algorithmic / combinatorial / matrix theoretic problem which is important in coding theory. The question, in my approximation, is this. Everything is over GF(2). Given a matrix A, find a not-so-much larger matrix A' with the same kernel as A (i.e., A, A' are parity check matrices for the same linear binary code), but such that for every set S of at least, say, r columns, there is a row which has exactly one 1 in S.

Yauhen will explain a known probabilistic construction which produces A' from A, plus improvements they made on it.