Combinatorial Optimization Using Tools from Convex Geometry
Event details
| Date | 05.07.2024 |
| Hour | 10:00 › 12:00 |
| Speaker | Neta Singer |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Friedrich Eisenbrand
Co-examiner: Prof. Michael Kapralov
Abstract
We study matrix rank bounds, frame scaling, and matroid $k$ parity via a survey of three recent advances in the areas. A frame scaling is a processing procedure on a dataset that distributes the datapoints evenly throughout the space. The scaling is a useful subroutine for learning theory methods and in deriving set bounds. We discuss a recent breakthrough that gives a strongly polynomial time algorithm for approximate frame scaling. We then discuss an application of frame scaling found for deriving rank bounds via a rescaling that maintains the rank of a matrix. The rank bound is used to bound the dimension of certain point configurations. We also discuss a local search method that gives a $k/2$-approximation algorithm for matroid $k$ parity. Such problems are canonical in combinatorial optimization, and notably exhibit novel and geometric techniques.
Background papers
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Friedrich Eisenbrand
Co-examiner: Prof. Michael Kapralov
Abstract
We study matrix rank bounds, frame scaling, and matroid $k$ parity via a survey of three recent advances in the areas. A frame scaling is a processing procedure on a dataset that distributes the datapoints evenly throughout the space. The scaling is a useful subroutine for learning theory methods and in deriving set bounds. We discuss a recent breakthrough that gives a strongly polynomial time algorithm for approximate frame scaling. We then discuss an application of frame scaling found for deriving rank bounds via a rescaling that maintains the rank of a matrix. The rank bound is used to bound the dimension of certain point configurations. We also discuss a local search method that gives a $k/2$-approximation algorithm for matroid $k$ parity. Such problems are canonical in combinatorial optimization, and notably exhibit novel and geometric techniques.
Background papers
- Strongly Polynomial Frame Scaling to High Precision. https://arxiv.org/pdf/2402.04799
- Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. https://dl.acm.org/doi/abs/10.1145/1993636.1993705
- Matroid Matching: the Power of Local Search. https://dl.acm.org/doi/pdf/10.1145/1806689.1806741
Practical information
- General public
- Free
Contact
- edic@epfl.ch