Name
Abstract | ||
|---|---|---|
We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a combining algorithm---an algorithm that maps a distribution over solutions into a (possibly weaker) solution---into a rounding algorithm that maps a solution of the relaxation to a solution of the original problem. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2591796.2591886 | STOC |
Keywords | DocType | Volume |
general,matching,differential privacy | Journal | abs/1312.6652 |
Citations | PageRank | References |
31 | 1.00 | 40 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boaz Barak | 1 | 2563 | 127.61 |
| Jonathan Kelner | 2 | 654 | 35.91 |
| David Steurer | 3 | 934 | 44.91 |