Show simple item record

dc.contributor.authorAllen-Zhu, Zeyuanen_US
dc.contributor.authorLee, Yin Taten_US
dc.contributor.authorOrecchia, Lorenzoen_US
dc.coverage.spatialSociety for Industrial and Applied Mathematicsen_US
dc.date.accessioned2019-12-19T18:34:33Z
dc.date.available2019-12-19T18:34:33Z
dc.date.issued2016
dc.identifier.citationZeyuan Allen-Zhu, Yin Tat Lee, Lorenzo Orecchia. 2016. "Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver." Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, https://doi.org/10.1137/1.9781611974331.ch127
dc.identifier.urihttps://hdl.handle.net/2144/39022
dc.description.abstractWe study the design of polylogarithmic depth algorithms for approximately solving packing and covering semidefinite programs (or positive SDPs for short). This is a natural SDP generalization of the well-studied positive LP problem. Although positive LPs can be solved in polylogarithmic depth while using only log2 n/∊3 parallelizable iterations [4], the best known positive SDP solvers due to Jain and Yao [18] require log14 n/∊13 parallelizable iterations. Several alternative solvers have been proposed to reduce the exponents in the number of iterations [19, 30]. However, the correctness of the convergence analyses in these works has been called into question [30], as they both rely on algebraic monotonicity properties that do not generalize to matrix algebra. In this paper, we propose a very simple algorithm based on the optimization framework proposed in [4] for LP solvers. Our algorithm only needs log2 n/∊3 iterations, matching that of the best LP solver. To surmount the obstacles encountered by previous approaches, our analysis requires a new matrix inequality that extends Lieb-Thirring's inequality, and a sign-consistent, randomized variant of the gradient truncation technique proposed in [3, 4].en_US
dc.format.extentp. 1824 - 1831en_US
dc.language.isoen_US
dc.relation.ispartofProceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
dc.subjectData structures and algorithmsen_US
dc.titleUsing optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solveren_US
dc.typeConference materialsen_US
dc.description.versionAccepted manuscripten_US
dc.identifier.doi10.1137/1.9781611974331.ch127
pubs.elements-sourcemanual-entryen_US
pubs.notesEmbargo: Not knownen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusPublisheden_US
dc.identifier.mycv72592


This item appears in the following Collection(s)

Show simple item record