Abstract: Matroids are combinatorial objects that generalize the notion of linear independence. They have several applications in design and analysis of algorithms. Linear matroids are a subclass of matroids that can be represented by a matrix. Recently, these matroids have found applications in Parameterized Complexity, including some breakthrough results. In this talk, we will discuss the problem of constructing a matrix representation of linear matroids, especially via deterministic algorithms.
