research
∙
11/14/2022
Low-depth arithmetic circuit lower bounds via shifted partials
We prove super-polynomial lower bounds for low-depth arithmetic circuits...
share
research
∙
10/22/2022
OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries
State-of-the-art algorithms for Approximate Nearest Neighbor Search (ANN...
research
∙
12/02/2021
Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
We study the complexity of optimizing highly smooth convex functions. Fo...
research
∙
10/05/2020
No quantum speedup over gradient descent for non-smooth convex optimization
We study the first-order convex optimization problem, where we have blac...
research
∙
09/06/2020
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
We give improved separations for the query complexity analogue of the lo...
research
∙
04/15/2020
Learning sums of powers of low-degree polynomials in the non-degenerate case
We develop algorithms for writing a polynomial as sums of powers of low ...
research
∙
10/27/2019
Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
This paper initiates a systematic development of a theory of non-commuta...
research
∙
10/02/2019
Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings
We consider the problem of outputting succinct encodings of lists of gen...
research
∙
04/08/2019
More barriers for rank methods, via a "numeric to symbolic" transfer
We prove new barrier results in arithmetic complexity theory, showing se...
research
∙
08/29/2018
Recent progress on scaling algorithms and applications
Scaling problems have a rich and diverse history, and thereby have found...
research
∙
07/17/2018
Classical lower bounds from quantum upper bounds
We prove lower bounds on complexity measures, such as the approximate de...
research
∙
04/12/2018
Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
We present a polynomial time algorithm to approximately scale tensors of...
research
∙
04/03/2018
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
We propose a new second-order method for geodesically convex optimizatio...
research
∙
11/21/2017
Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
Alternating minimization heuristics seek to solve a (difficult) global o...
research
∙
10/26/2017
Barriers for Rank Methods in Arithmetic Complexity
Arithmetic complexity is considered simpler to understand than Boolean c...
research
∙
03/02/2017
Adapting the DMTCP Plugin Model for Checkpointing of Hardware Emulation
Checkpoint-restart is now a mature technology. It allows a user to save ...
research
∙
06/24/2015