ÍâÍøÌìÌÃ

I will present fast practical algorithms for approximate semidefinite programming (SDP) based on regularization by the von Neumann entropy. These approachesÌýare based on a dual formulation of the regularized problem,Ìýand dual updates are computed using randomized trace estimators. Since the primal variable is only represented implicitly and we deliberately want to avoidÌýassumptions of low-rankness, some care is required to recover problem-specific desiderata from the dual solution. I will show how the full pipeline yields fast algorithms for the Max-Cut problem, spectral embedding, and the full/partial permutation synchronization problems.