Theory of Computing ------------------- Title : A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs Authors : Shayan Oveis Gharan and Luca Trevisan Volume : 11 Number : 9 Pages : 241-256 URL : https://theoryofcomputing.org/articles/v011a009 Abstract -------- Kolla and Tulsiani (2007, 2011) and Arora, Barak and Steurer (2010) introduced the technique of _subspace enumeration_, which gives approximation algorithms for graph problems such as unique games and small set expansion; the running time of such algorithms is exponential in the _threshold-rank_ of the graph. Guruswami and Sinop (2011, 2012) and Barak, Raghavendra, and Steurer (2011) developed an alternative approach to the design of approximation algorithms for graphs of bounded threshold-rank based on semidefinite programming relaxations obtained by using sum-of-squares hierarchy (2000, 2001) and on novel rounding techniques. These algorithms are faster than the ones based on subspace enumeration and work on a broad class of problems. In this paper we develop a third approach to the design of such algorithms. We show, constructively, that graphs of bounded threshold- rank satisfy a _weak Szemeredi regularity lemma_ analogous to the one proved by Frieze and Kannan (1999) for dense graphs. The existence of efficient approximation algorithms is then a consequence of the regularity lemma, as shown by Frieze and Kannan. Applying our method to the Max Cut problem, we devise an algorithm that is slightly faster than all previous algorithms, and is easier to describe and analyze. An extended abstract of this paper appeared in the proceedings of the 16th International Workshop on Approxiation Algorithms for Combinatorial Optimization Problems (APPROX 2013).