83 citations · 303 across the 25 of their papers we have counts for
31 papers
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy +1
We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, ) trade-off…
An Optimal "It Ain't Over Till It's Over" Theorem
Ronen Eldan, Avi Wigderson, Pei Wu
We study the probability of Boolean functions with small max influence to become constant under random restrictions. Let be a Boolean function such that the variance of is…
Connections between graphs and matrix spaces
Yinan Li, Youming Qiao, Avi Wigderson +2
Given a bipartite graph , the graphical matrix space consists of matrices whose non-zero entries can only be at those positions corresponding to edges in . Tu…
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing
Oded Goldreich, Avi Wigderson
A graph is called self-ordered (a.k.a asymmetric) if the identity permutation is its only automorphism. Equivalently, there is a unique isomorphism from to any graph that i…
Polynomial time algorithms in invariant theory for torus actions
Peter Bürgisser, M. Levent Doğan, Visu Makam +2
An action of a group on a vector space partitions the latter into a set of orbits. We consider three natural and useful algorithmic "isomorphism" or "classification" problems, name…
On the Power and Limitations of Branch and Cut
Noah Fleming, Mika Göös, Russell Impagliazzo +4
The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simul…