5 citations · 22 across the 17 of their papers we have counts for
6 papers · 1 filter
Nonlinear Random Matrices and Applications to the Sum of Squares Hierarchy
Goutham Rajendran
We develop new tools in the theory of nonlinear random matrices and apply them to study the performance of the Sum of Squares (SoS) hierarchy on average-case problems. The SoS hier…
Concentration of polynomial random matrices via Efron-Stein inequalities
Goutham Rajendran, Madhur Tulsiani
Analyzing concentration of large random matrices is a common task in a wide variety of fields. Given independent random variables, many tools are available to analyze random matric…
Combinatorial Optimization via the Sum of Squares Hierarchy
Goutham Rajendran
We study the Sum of Squares (SoS) Hierarchy with a view towards combinatorial optimization. We survey the use of the SoS hierarchy to obtain approximation algorithms on graphs usin…
Sum-of-Squares Lower Bounds for Sparse Independent Set
Chris Jones, Aaron Potechin, Goutham Rajendran +2
The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful algorithmic paradigm which captures state-of-the-art algorithmic guarantees for a wide array of problems.…
Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems
Aaron Potechin, Goutham Rajendran
In this paper, we construct general machinery for proving Sum-of-Squares lower bounds on certification problems by generalizing the techniques used by Barak et al. [FOCS 2016] to p…
Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes
Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones +2
The Sum-of-Squares (SoS) hierarchy is a semi-definite programming meta-algorithm that captures state-of-the-art polynomial time guarantees for many optimization problems such as Ma…