Doctoral Speaking Skills - Madhusudan Reddy Pittu

— 11:30am

Location:
In Person - Gates Hillman 8102

Speaker:
MADHUSUDHAN REDDY PITTU, Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://mathrulestheworld.github.io/

Determinant maximization provides an elegant generalization of problems in many areas, including convex geometry, statistics, machine learning, fair allocation of goods, and network design.In an instance of the determinant maximization problem, we are given a collection of vectors $v_1,\ldots, v_n \in \mathbb{R}^d$, and the goal is to pick a subset $S\subseteq [n]$ of given vectors to maximize the determinant of the matrix $\sum_{i \in S} v_iv_i^\top$, where the picked set of vectors $S$ must satisfy some combinatorial constraint such as cardinality constraint ($|S| \leq k$) or matroid constraint ($S$ is a basis of a matroid defined on $[n]$).

We give efficient deterministic combinatorial algorithms for the determinant maximization problem under a matroid constraint that achieves $O(r^{O(r)})$-approximation for any matroid of rank $r\leq d$ and $O(d^O(d))$-approximation for any matroid of rank $r\geq d$. The algorithm for the $r\leq d$ case relies on the geometric interpretation of the determinant whereas the algorithm for the $r\geq d$ case relies on the algebraic properties of the determinant and the properties of a convex programming relaxation introduced by Madan et al. (FOCS '20). In both cases, we use matroid intersection as a local search tool to iteratively improve a solution by finding an alternating negative cycle in an appropriately defined exchange graph defined by the matroids.

Joint work with Adam Brown, Aditi Laddha, Mohit Singh, and Prasad Tetali.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement


Add event to Google
Add event to iCal