{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:41:03Z","timestamp":1725745263841},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403279"},{"type":"electronic","value":"9783642403286"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_22","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T09:17:34Z","timestamp":1376644654000},"page":"303-316","source":"Crossref","is-referenced-by-count":1,"title":["A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs"],"prefix":"10.1007","author":[{"given":"Shayan","family":"Oveis Gharan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Trevisan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. In: FOCS, pp. 563\u2013572 (2010)","DOI":"10.1109\/FOCS.2010.59"},{"issue":"4","key":"22_CR2","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1137\/S0097539704441629","volume":"35","author":"N. Alon","year":"2006","unstructured":"Alon, N., Naor, A.: Approximating the cut-norm via grothendieck\u2019s inequality. SIAM J. Comput.\u00a035(4), 787\u2013803 (2006)","journal-title":"SIAM J. Comput."},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Barak, B., Raghavendra, P., Steurer, D.: Rounding semidefinite programming hierarchies via global correlation. In: FOCS, pp. 472\u2013481 (2011)","DOI":"10.1109\/FOCS.2011.95"},{"key":"22_CR4","first-page":"207","volume-title":"SODA","author":"A. Coja-Oghlan","year":"2009","unstructured":"Coja-Oghlan, A., Cooper, C., Frieze, A.: An efficient sparse regularity concept. In: SODA, pp. 207\u2013216. Society for Industrial and Applied Mathematics, Philadelphia (2009)"},{"key":"22_CR5","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1145\/1060590.1060701","volume-title":"STOC","author":"W. Fernandez De la Vega","year":"2005","unstructured":"Fernandez De la Vega, W., Karpinski, M., Kannan, R., Vempala, S.: Tensor decomposition and approximation schemes for constraint satisfaction problems. In: STOC, pp. 747\u2013754. ACM, New York (2005)"},{"key":"22_CR6","first-page":"12","volume-title":"FOCS","author":"A.M. Frieze","year":"1996","unstructured":"Frieze, A.M., Kannan, R.: The regularity lemma and approximation schemes for dense problems. In: FOCS, p. 12. IEEE Computer Society, Washington, DC (1996)"},{"issue":"2","key":"22_CR7","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s004930050052","volume":"19","author":"A.M. Frieze","year":"1999","unstructured":"Frieze, A.M., Kannan, R.: Quick approximation to matrices and applications. Combinatorica\u00a019(2), 175\u2013220 (1999)","journal-title":"Combinatorica"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sinop, A.K.: Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives. In: FOCS, pp. 482\u2013491 (2011)","DOI":"10.1109\/FOCS.2011.36"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sinop, A.K.: Faster sdp hierarchy solvers for local rounding algorithms. In: FOCS (2012)","DOI":"10.1109\/FOCS.2012.58"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sinop, A.K.: Lasserre sdps, l1-embeddings, and approximating non-uniform sparsest cut via generalized spectra. In: SODA (2013)","DOI":"10.1137\/1.9781611973105.22"},{"issue":"6","key":"22_CR11","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM\u00a042(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"2","key":"22_CR12","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s00037-011-0011-7","volume":"20","author":"A. Kolla","year":"2011","unstructured":"Kolla, A.: Spectral algorithms for unique games. Comput. Complex.\u00a020(2), 177\u2013206 (2011)","journal-title":"Comput. Complex."},{"key":"22_CR13","unstructured":"Kolla, A., Tulsiani, M.: Playing unique games using graph spectra. Manuscript (2007)"},{"key":"22_CR14","series-title":"Colloq. Internat. CNRS","first-page":"399","volume-title":"Problemes Combinatoires et Theorie des Graphes","author":"E. Szemeredi","year":"1978","unstructured":"Szemeredi, E.: Regular partitions of graphs. In: Problemes Combinatoires et Theorie des Graphes. Colloq. Internat. CNRS, vol.\u00a0260, pp. 399\u2013401. CNRS, Paris (1978)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,3]],"date-time":"2023-07-03T18:33:55Z","timestamp":1688409235000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}