54 citations · 151 across the 13 of their papers we have counts for
5 papers · 1 filter
A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees
Tarun Kathuria
Let be positive semidefinite matrices of rank at most , with and $\norm{A_i}\le\varepsilon$. We prove that one sign can be assigned to each origi…
A Faster Interior Point Method for Semidefinite Programming
Haotian Jiang, Tarun Kathuria, Yin Tat Lee +2
Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, a…
A Potential Reduction Inspired Algorithm for Exact Max Flow in Almost Time
Tarun Kathuria
We present an algorithm for computing - maximum flows in directed graphs in time. Our algorithm is inspired by potential reduction interi…
On the Complexity of Constrained Determinantal Point Processes
L. Elisa Celis, Amit Deshpande, Tarun Kathuria +2
Determinantal Point Processes (DPPs) are probabilistic models that arise in quantum physics and random matrix theory and have recently found numerous applications in computer scien…
On Sampling and Greedy MAP Inference of Constrained Determinantal Point Processes
Tarun Kathuria, Amit Deshpande
Subset selection problems ask for a small, diverse yet representative subset of the given data. When pairwise similarities are captured by a kernel, the determinants of submatrices…