Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver

Understand

We 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 $\tilde{O}(\log^{2} n/\varepsilon^2)$ parallelizable iterations, the best known positive SDP solvers due to Jain and Yao require $O(\log^{14} n /\varepsilon^{13})$ parallelizable iterations.
• Several alternative solvers have been proposed to reduce the exponents in the number of iterations.