{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:28:03Z","timestamp":1787340483972,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We deal with two intimately related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to express how much a given graph \u201cresembles\u201d a random one. Moreover, a regular partition approximates a given graph by a bounded number of quasi-random graphs. Regarding quasi-randomness, we present a new spectral characterization of low discrepancy, which extends to sparse graphs. Concerning regular partitions, we introduce a concept of regularity that takes into account vertex weights, and show that if $G=(V,E)$ satisfies a certain boundedness condition, then G admits a regular partition. In addition, building on the work of Alon and Naor [Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, IL, ACM, New York, 2004, pp. 72\u201380], we provide an algorithm that computes a regular partition of a given (possibly sparse) graph G in polynomial time. As an application, we present a polynomial time approximation scheme for MAX CUT on (sparse) graphs without \u201cdense spots.\u201d<\/jats:p>","DOI":"10.1137\/070709529","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T18:08:11Z","timestamp":1270663691000},"page":"2336-2362","source":"Crossref","is-referenced-by-count":20,"title":["Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions"],"prefix":"10.1137","volume":"39","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amin","family":"Coja-Oghlan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hi\u00eap","family":"H\u00e0n","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihyun","family":"Kang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vojt\u011bch","family":"R\u00f6dl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mathias","family":"Schacht","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,4,7]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.74.47"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0805002"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Alon and A. Naor,\n                      Approximating the cut-norm via Grothendieck's inequality\n                      , in Proceedings of the 36th ACM Symposium on Theory of Computing, Chicago, IL, ACM, New York, 2004, pp. 72\u201380.","DOI":"10.1145\/1007352.1007371"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"R. Bellman,\n                      Introduction to Matrix Analysis\n                      , 2nd ed., Classics in Appl. Math. 19, SIAM, Philadelphia, 1997.","DOI":"10.1137\/1.9781611971170"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0029-7"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2004.05.006"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.05.015"},{"key":"R9","unstructured":"F. Chung,\n                      Spectral Graph Theory\n                      , American Mathematical Society, Providence, RI, 1997."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20188"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200010"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125347"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579329"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"S. Gerke and A. Steger,\n                      The sparse regularity lemma and its applications\n                      , in Proceedings of the 20th British Combinatorial Conference, Surveys in Combinatorics, London Math. Soc. Lecture Note Ser. 327, B. S. Webb, ed., Cambridge University Press, Cambridge, UK, 2005, pp. 227\u2013258.","DOI":"10.1017\/CBO9780511734885.010"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"S. Gerke and A. Steger,\n                      A characterization for sparse $\\eps$-regular pairs\n                      , Electron. J. Combin., 14 (2007), paper R4.","DOI":"10.37236\/923"},{"key":"R17","first-page":"1","volume":"8","author":"Grothendieck A.","year":"1953","journal-title":"Bol. Soc. Mat. Sao Paulo"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Springer, New York, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"R20","unstructured":"C. Helmberg,\n                      Semidefinite Programming for Combinatorial Optimization\n                      , Habilitation thesis, Report ZR-00-34, Zuse Institute, Berlin, 2000."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Y. Kohayakawa,\n                      Szemer\u00e9di's regularity lemma for sparse graphs\n                      , in Foundations of Computational Mathematics, F. Cucker and M. Shub, eds., Springer, New York, 1997, pp. 216\u2013230.","DOI":"10.1007\/978-3-642-60539-0_16"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408223"},{"key":"R23","unstructured":"E. Szemer\u00e9di,\n                      Regular partitions of graphs\n                      , in Probl\u00e9mes Combinatoires et Th\u00e9orie des Graphes, Colloq. Internat. CNRS 260, CNRS, Paris, 1978, pp. 399\u2013401."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797328847"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070709529","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:36:39Z","timestamp":1787337399000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070709529"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/070709529"],"URL":"https:\/\/doi.org\/10.1137\/070709529","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}