
Polynomial time algorithms in invariant theory for torus actions
An action of a group on a vector space partitions the latter into a set ...
read it

On the Power and Limitations of Branch and Cut
The Stabbing Planes proof system was introduced to model the reasoning c...
read it

The uncertainty principle: variations on a theme
We show how a number of wellknown uncertainty principles for the Fourie...
read it

Towards a theory of noncommutative optimization: geodesic first and second order methods for moment maps and polytopes
This paper initiates a systematic development of a theory of noncommuta...
read it

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...
read it

Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties)
The following multideterminantal algebraic variety plays a central role...
read it

More barriers for rank methods, via a "numeric to symbolic" transfer
We prove new barrier results in arithmetic complexity theory, showing se...
read it

Subspace arrangements, graph rigidity and derandomization through submodular optimization
This paper presents a deterministic, strongly polynomial time algorithm ...
read it

Spanoids  an abstraction of spanning structures, and a barrier for LCCs
We introduce a simple logical inference structure we call a spanoid (gen...
read it

Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
We present a polynomial time algorithm to approximately scale tensors of...
read it

Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
We propose a new secondorder method for geodesically convex optimizatio...
read it

Alternating minimization, scaling algorithms, and the nullcone problem from invariant theory
Alternating minimization heuristics seek to solve a (difficult) global o...
read it

Interactions of Computational Complexity Theory and Mathematics
[This paper is a (self contained) chapter in a new book, Mathematics an...
read it

Barriers for Rank Methods in Arithmetic Complexity
Arithmetic complexity is considered simpler to understand than Boolean c...
read it
Avi Wigderson
is this you? claim profile