research
∙
12/26/2022
On linear-algebraic notions of expansion
A fundamental fact about bounded-degree graph expanders is that three no...
share
research
∙
09/15/2022
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
We give an efficient algorithm that transforms any bounded degree expand...
research
∙
08/06/2022
An Optimal "It Ain't Over Till It's Over" Theorem
We study the probability of Boolean functions with small max influence t...
research
∙
06/09/2022
Connections between graphs and matrix spaces
Given a bipartite graph G, the graphical matrix space 𝒮_G consists of ma...
research
∙
12/01/2021
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing
A graph G is called self-ordered (a.k.a asymmetric) if the identity perm...
research
∙
02/15/2021
Polynomial time algorithms in invariant theory for torus actions
An action of a group on a vector space partitions the latter into a set ...
research
∙
02/09/2021
On the Power and Limitations of Branch and Cut
The Stabbing Planes proof system was introduced to model the reasoning c...
research
∙
06/19/2020
The uncertainty principle: variations on a theme
We show how a number of well-known uncertainty principles for the Fourie...
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
∙
09/02/2019
Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties)
The following multi-determinantal algebraic variety plays a central role...
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
∙
01/27/2019
Subspace arrangements, graph rigidity and derandomization through submodular optimization
This paper presents a deterministic, strongly polynomial time algorithm ...
research
∙
09/27/2018
Spanoids - an abstraction of spanning structures, and a barrier for LCCs
We introduce a simple logical inference structure we call a spanoid (gen...
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
Interactions of Computational Complexity Theory and Mathematics
[This paper is a (self contained) chapter in a new book, Mathematics an...
research
∙
10/26/2017