Description
Combinatorics Seminar.
Speaker: Pranabendu Misra.
Affiliation: Max-Planck Institute for Informatics.
Date and Time: Wednesday 05 February, 11:00 am - 12:30 pm.
Venue: Ramanujan Hall, Department of Mathematics.
Title: Deterministic Representation of Linear Matroids.
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.