16 citations · 16 across the 1 of their papers we have counts for
7 papers
Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings
Ankit Garg, Christian Ikenmeyer, Visu Makam +3
We consider the problem of computing succinct encodings of lists of generators for invariant rings for group actions. Mulmuley conjectured that there are always polynomial sized su…
More barriers for rank methods, via a "numeric to symbolic" transfer
Ankit Garg, Visu Makam, Rafael Oliveira +1
We prove new barrier results in arithmetic complexity theory, showing severe limitations of natural lifting (aka escalation) techniques. For example, we prove that even optimal ran…
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
Mrinal Kumar, Rafael Oliveira, Ramprasad Saptharishi
We show that any -variate polynomial computable by a syntactically multilinear circuit of size can be computed by a depth- syntactically multilinear…
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…
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…