View article

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 log² n/∊³ parallelizable iterations [4], the best known positive SDP solvers due to Jain and Yao [18] require log¹⁴ n/∊¹³ 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 log² n/∊³ …