Rohan Kapadia

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.