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.
Discrete Lunch >