A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs

Shayan Oveis Gharan, Luca Trevisan

Kolla and Tulsiani [KT07,Kolla11} and Arora, Barak and Steurer [ABS10] introduced the technique of subspace enumeration, which gives approximation algorithms for graph problems suc…