Name
Abstract | ||
|---|---|---|
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. In the average case setting, SoS lower bounds provide strong evidence of algorithmic hardness or information-computation gaps. Prior to this work, SoS lower bounds have been obtained for problems in the “dense” input reg... |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1109/FOCS52979.2021.00048 | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Computer science,Particle separators,Random variables,Sparse matrices | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-1-6654-2055-6 | 1 | 0.35 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chris Jones | 1 | 278 | 44.53 |
| Aaron Potechin | 2 | 2 | 1.04 |
| Goutham Rajendran | 3 | 2 | 0.70 |
| Madhur Tulsiani | 4 | 358 | 24.60 |
| Jeff Xu | 5 | 1 | 0.35 |