Monday, October 20th, 2014 4pm-5pm Burnside 1205
Concordia University
Finding shortest circuits in binary matroids

Given a set of n binary vectors of length r, can we find the size of the smallest linearly dependent subset? While this problem is NP-hard, it is easy in certain cases: if each vector has at most two ones, then it reduces to computing the girth of a graph, or equivalently, of a graphic matroid. In fact, this problem is equivalent to the problem of computing the girth of a binary matroid or the minimum distance of a binary linear code. In this talk, I will discuss solving this problem for binary matroids from any given minor-closed class. In particular, I will describe randomized algorithms to do so for binary matroids that are "almost" graphic or cographic. No knowledge of matroids will be assumed. This is joint work with Jim Geelen.

Fall 2014 Schedule