64 citations · 131 across the 9 of their papers we have counts for
16 papers
Robust Radical Sylvester-Gallai Theorem for Quadratics
Abhibhav Garg, Rafael Oliveira, Akash Sengupta
We prove a robust generalization of a Sylvester-Gallai type theorem for quadratic polynomials, generalizing the result in [S'20]. More precisely, given a parameter an…
Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
Peter Bürgisser, Cole Franks, Ankit Garg +3
This paper initiates a systematic development of a theory of non-commutative optimization. It aims to unify and generalize a growing body of work from the past few years which deve…
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…
Barriers for Rank Methods in Arithmetic Complexity
Klim Efremenko, Ankit Garg, Rafael Oliveira +1
Arithmetic complexity is considered simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly m…
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…
Rank bounds for design matrices with block entries and geometric applications
Zeev Dvir, Ankit Garg, Rafael Oliveira +1
Design matrices are sparse matrices in which the supports of different columns intersect in a few positions. Such matrices come up naturally when studying problems involving point…
Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling
Ankit Garg, Leonid Gurvits, Rafael Oliveira +1
The celebrated Brascamp-Lieb (BL) inequalities (and their extensions) are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geomet…
Operator scaling: theory and applications
Ankit Garg, Leonid Gurvits, Rafael Oliveira +1
In this paper we present a deterministic polynomial time algorithm for testing if a symbolic matrix in non-commuting variables over is invertible or not. The analogous…
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
Rafael Oliveira, Amir Shpilka, Ben Lee Volk
In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain…
Factors of Sparse Polynomials are Sparse
Zeev Dvir, Rafael Mendes de Oliveira
This paper was removed due to an error in the proof (Claim 4.12 as stated is not true). The authors would like to thank Ilya Volkovich for pointing out a counterexample to this pap…
Testing Equivalence of Polynomials under Shifts
Zeev Dvir, Rafael Oliveira, Amir Shpilka
Two polynomials are called shift-equivalent if there exists a vector such that the polynomial identity…