Seminars

View all Seminars  |  Download ICal for this event

Sparsifying Sums of Positive Semidefinite Matrices

Series: Bangalore Theory Seminars

Speaker: Pravesh Kothari, Princeton University

Date/Time: Jan 15 23:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Abstract:
I will talk about a new instance-specific sparsification theorem for sums of PSD matrices. As a corollary, I will show that every Cayley graph on any group has a weighted Cayley sparsifier with O(log^4 |G|) generators.

Based on joint work with Arpon Basu (Princeton), Yang Liu (CMU), and Raghu Meka (UCLA).


Microsoft Teams link:

Link

We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Debajyoti Kar, Rameesh Paul, Nirjhar Das, KVN Sreenivas, Rahul Madhavan