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

by Shayan Oveis Gharan and Luca Trevisan

Theory of Computing, Volume 11(9), pp. 241-256, 2015

Bibliography with links to cited articles

[1]   Noga Alon and Assaf Naor: Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput., 35(4):787–803, 2006. Preliminary version in STOC’04. [doi:10.1137/S0097539704441629]

[2]   Sanjeev Arora, Boaz Barak, and David Steurer: Subexponential algorithms for Unique Games and related problems. In Proc. 51st FOCS, pp. 563–572. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.59]

[3]   Boaz Barak, Prasad Raghavendra, and David Steurer: Rounding semidefinite programming hierarchies via global correlation. In Proc. 52nd FOCS, pp. 472–481. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.95]

[4]   Amin Coja-Oghlan, Colin Cooper, and Alan M. Frieze: An efficient sparse regularity concept. SIAM J. Discrete Math., 23(4):2000–2034, 2010. Preliminary version in SODA’09. [doi:10.1137/080730160]

[5]   Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, and Santosh Vempala: Tensor decomposition and approximation schemes for constraint satisfaction problems. In Proc. 37th STOC, pp. 747–754. ACM Press, 2005. [doi:10.1145/1060590.1060701]

[6]   Alan M. Frieze and Ravi Kannan: The regularity lemma and approximation schemes for dense problems. In Proc. 37th FOCS, pp. 12–20. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548459]

[7]   Alan M. Frieze and Ravi Kannan: Quick approximation to matrices and applications. Combinatorica, 19(2):175–220, 1999. [doi:10.1007/s004930050052]

[8]    Michel X. Goemans and David P. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, 1995. Preliminary version in STOC’94. [doi:10.1145/227683.227684]

[9]   Venkatesan Guruswami and Ali Kemal Sinop: Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives. In Proc. 52nd FOCS, pp. 482–491. IEEE Comp. Soc. Press, 2011. Expanded version in CoRR (2011). Merged with [11] in CoRR (2013). [doi:10.1109/FOCS.2011.36]

[10]   Venkatesan Guruswami and Ali Kemal Sinop: Faster SDP hierarchy solvers for local rounding algorithms. In Proc. 53rd FOCS, pp. 197–206. IEEE Comp. Soc. Press, 2012. Expanded version in CoRR. [doi:10.1109/FOCS.2012.58]

[11]   Venkatesan Guruswami and Ali Kemal Sinop: Approximating non-uniform sparsest cut via generalized spectra. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13). SIAM, 2013. Expanded version, merged with [9] in CoRR (2013). [doi:10.1137/1.9781611973105.22]

[12]   Alexandra Kolla: Spectral algorithms for Unique Games. Comput. Complexity, 20(2):177–206, 2011. Preliminary versions in CCC’10 and ECCC (2010). [doi:10.1007/s00037-011-0011-7]

[13]   Alexandra Kolla and Madhur Tulsiani: Playing Unique Games using graph spectra. manuscript, 2007.

[14]   Jean B. Lasserre: Global optimization with polynomials and the problem of moments. SIAM J. Optim., 11(3):796–817, 2001. [doi:10.1137/S1052623400366802]

[15]   Shayan Oveis Gharan and Luca Trevisan: A new regularity lemma and faster approximation algorithms for low threshold rank graphs. In Proc. 16th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’13), pp. 303–316, 2013. [doi:10.1007/978-3-642-40328-6_22]

[16]   Pablo A. Parrilo: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph. D. thesis, California Institute of Technology, 2000.

[17]   Endre Szemerédi: Regular partitions of graphs. Colloq. Internat. CNRS: Problèmes Combinatoires et Théorie des Graphes, 260:399–401, 1978.