Subgaussian Vector Balancing by an Ising Model

Heng Guo, Daniel A. Spielman, Xinyuan Zhang

We show that the guaranties of the Gram-Schmidt Walk Algorithm of Bansal, Dadush, Garg, and Lovett can be achieved by an Ising model. Given vectors $v_1,\dots ,v_n$ of norm less…