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).