83 citations · 303 across the 25 of their papers we have counts for
5 papers · 1 filter
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy +1
We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, ) trade-off…
Polynomial time algorithms in invariant theory for torus actions
Peter Bürgisser, M. Levent Doğan, Visu Makam +2
An action of a group on a vector space partitions the latter into a set of orbits. We consider three natural and useful algorithmic "isomorphism" or "classification" problems, name…
Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
Peter Bürgisser, Cole Franks, Ankit Garg +3
We present a polynomial time algorithm to approximately scale tensors of any format to arbitrary prescribed marginals (whenever possible). This unifies and generalizes a sequence o…
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li +2
We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scalin…
Much Faster Algorithms for Matrix Scaling
Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira +1
We develop several efficient algorithms for the classical \emph{Matrix Scaling} problem, which is used in many diverse areas, from preconditioning linear systems to approximation o…