We show that the feasibility of a system of $m$ linear inequalities
over the cone of symmetric positive semidefinite matrices of order
$n$ can be tested in $mn^{O(\min\{m,n^2\})}$ arithmetic operations
over $ln^{O(\min\{m,n^2\})}$-bit numbers, where $l$ is the maximum
binary size of the input coefficients. We also show that any feasible
system of dimension $(n,m)$ has a solution $\M{X}$ such that
$\log \|\M{X}\| \le ln^{O(\min\{m,n^2\})}$.
DIMACS Home Page