16 citations · 20 across the 6 of their papers we have counts for
4 papers · 1 filter
Recent progress on scaling algorithms and applications
Ankit Garg, Rafael Oliveira
Scaling problems have a rich and diverse history, and thereby have found numerous applications in several fields of science and engineering. For instance, the matrix scaling proble…
Classical lower bounds from quantum upper bounds
Shalev Ben-David, Adam Bouland, Ankit Garg +1
We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove t…
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…