23 citations · 101 across the 39 of their papers we have counts for
6 papers · 1 filter
Graph Clustering using Effective Resistance
Vedat Levi Alev, Nima Anari, Lap Chi Lau +1
We design a polynomial time algorithm that for any weighted undirected graph $G = (V, E,\vecc w)$ and sufficiently large , partitions into…
Structured Robust Submodular Maximization: Offline and Online Algorithms
Alfredo Torrico, Mohit Singh, Sebastian Pokutta +4
Constrained submodular function maximization has been used in subset selection problems such as selection of most informative sensor locations. While these models have been quite p…
Planar Graph Perfect Matching is in NC
Nima Anari, Vijay V. Vazirani
Is perfect matching in NC? That is, is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in theoretical computer science for over thr…
Approximating the Largest Root and Applications to Interlacing Families
Nima Anari, Shayan Oveis Gharan, Amin Saberi +1
We study the problem of approximating the largest root of a real-rooted polynomial of degree using its top coefficients and give nearly matching upper and lower bounds. We…
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
Nima Anari, Leonid Gurvits, Shayan Oveis Gharan +1
We design a deterministic polynomial time approximation algorithm for the permanent of positive semidefinite matrices where . We write a natural convex…
A Generalization of Permanent Inequalities and Applications in Counting and Optimization
Nima Anari, Shayan Oveis Gharan
A polynomial is real stable if it has no roots in the upper-half complex plane. Gurvits's permanent inequality gives a lower bound on the coefficien…