- Series
- ACO Student Seminar
- Time
- Friday, February 17, 2023 - 1:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Adam Brown – Georgia Tech Math – ajmbrown@gatech.edu – https://sites.google.com/view/ajmbrown/
- Organizer
- Abhishek Dhawan
In the minimum eigenvalue problem we are given a collection of rank-1 symmetric matrices, and the goal is to find a subset whose sum has large minimum eigenvalue, subject to some combinatorial constraints. The constraints on which subsets we can select, could be cardinality, partition, or more general matroid base constraints. Using pipage rounding and a matrix concentration inequality, we will show a randomised algorithm which achieves a (1- epsilon) approximation for the minimum eigenvalue problem when the matrices have constant size, subject to any matroid constraint.
The bulk of the talk will be background on “pipage rounding, pessimistic estimators and matrix concentration” adapted from the paper with that title by Nicholas J. A. Harvey and Neil Olver. The application to the minimum eigenvalue problem is joint work with Aditi Laddha and Mohit Singh.