Please use this identifier to cite or link to this item:
https://doi.org/10.4086/toc.2014.v010a011
DC Field | Value | |
---|---|---|
dc.title | Efficient rounding for the noncommutative grothendieck inequality | |
dc.contributor.author | Naor, A | |
dc.contributor.author | Regev, O | |
dc.contributor.author | Vidick, T | |
dc.date.accessioned | 2020-10-27T11:04:11Z | |
dc.date.available | 2020-10-27T11:04:11Z | |
dc.date.issued | 2014 | |
dc.identifier.citation | Naor, A, Regev, O, Vidick, T (2014). Efficient rounding for the noncommutative grothendieck inequality. Theory of Computing 10 : 257-295. ScholarBank@NUS Repository. https://doi.org/10.4086/toc.2014.v010a011 | |
dc.identifier.issn | 15572862 | |
dc.identifier.uri | https://scholarbank.nus.edu.sg/handle/10635/181483 | |
dc.description.abstract | The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a polynomial-time constant-factor approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principal component analysis and the orthogonal Procrustes problem. © 2014 Assaf Naor, Oded Regev, and Thomas Vidick. | |
dc.rights | Attribution 4.0 International | |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | |
dc.source | Unpaywall 20201031 | |
dc.type | Article | |
dc.contributor.department | CENTRE FOR QUANTUM TECHNOLOGIES | |
dc.description.doi | 10.4086/toc.2014.v010a011 | |
dc.description.sourcetitle | Theory of Computing | |
dc.description.volume | 10 | |
dc.description.page | 257-295 | |
Appears in Collections: | Elements Staff Publications |
Show simple item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
10_4086_toc_2014_v010a011.pdf | 397.28 kB | Adobe PDF | OPEN | None | View/Download |
This item is licensed under a Creative Commons License