{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:24:21Z","timestamp":1787325861688,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Let ${\\bf A}$ be a $0\/1$ matrix of size $m\\times n$, and let p be the density of ${\\bf A}$ (i.e., the number of ones divided by $m\\cdot n$). We show that ${\\bf A}$ can be approximated in the cut norm within $\\varepsilon\\cdot mnp$ by a sum of cut matrices (of rank 1), where the number of summands is independent of the size $m\\cdot n$ of ${\\bf A}$, provided that ${\\bf A}$ satisfies a certain boundedness condition. This decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan [Combinatorica, 19 (1999), pp. 175\u2013220] to sparse matrices. As an application, we obtain efficient $1-\\varepsilon$ approximation algorithms for \u201cbounded\u201d instances of MAX CSP problems.<\/jats:p>","DOI":"10.1137\/080730160","type":"journal-article","created":{"date-parts":[[2010,1,7]],"date-time":"2010-01-07T20:05:13Z","timestamp":1262894713000},"page":"2000-2034","source":"Crossref","is-referenced-by-count":17,"title":["An Efficient Sparse Regularity Concept"],"prefix":"10.1137","volume":"23","author":[{"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Colin","family":"Cooper","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,1,6]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"N. Alon, A. Coja-Oghlan, H. Han, M. Kang, V. R\u00f6dl, and M. Schacht,\n                      Quasi-randomness and algorithmic regularity for graphs with general degree distributions\n                      , in Proceedings of the 34th International Colloquium on Automata, Languages and Programming, 2007, pp. 789\u2013800.","DOI":"10.1007\/978-3-540-73420-8_68"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00008-4"},{"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 Annual ACM Symposium on Theory of Computing, 2004, pp. 72\u201380.","DOI":"10.1145\/1007352.1007371"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1605"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"R. Boppana,\n                      Eigenvalues and graph bisection: An average-case analysis\n                      , in Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 280\u2013285.","DOI":"10.1109\/SFCS.1987.22"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20116"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830600784X"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793247634"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"U. Feige,\n                      Relations between average case complexity and approximation complexity\n                      , in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 534\u2013543.","DOI":"10.1145\/509907.509985"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"U. Feige, J.H. Kim, and E. Ofek,\n                      Witnesses for non-satisfiability of dense random 3CNF formulas\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 497\u2013508.","DOI":"10.1109\/FOCS.2006.78"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"U. Feige and E. Ofek,\n                      Easily refutable subformulas of large random 3CNF formulas\n                      , in Proceedings of the 31st International Colloquium on Automata, Languages and Programming, 2004, pp. 519\u2013530.","DOI":"10.1007\/978-3-540-27836-8_45"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"W. Fernandez de la Vega, R. Kannan, M. Karpinski, and S. Vempala,\n                      Tensor decomposition and approximation algorithms for constraint satisfaction problems\n                      , in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 747\u2013754.","DOI":"10.1145\/1060590.1060701"},{"key":"R15","unstructured":"A. Flaxman,\n                      A spectral technique for random satisfiable 3CNF formulas\n                      , in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 357\u2013363."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444096X"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"S. Gerke and A. Steger,\n                      The sparse regularity lemma and its applications\n                      , in Surveys in Combinatorics, B. Webb, ed., Cambridge University Press, Cambridge, UK, 2005, pp. 227\u2013258.","DOI":"10.1017\/CBO9780511734885.010"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001621"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"S. Khot, G. Kindler, E. Mossel, and R. O'Donnell,\n                      Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?\n                      , in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 146\u2013154.","DOI":"10.1109\/FOCS.2004.49"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Y. Kohayakawa,\n                      's regularity lemma for sparse graphs\n                      , in Foundations of Computational Mathematics, F. Cucker and M. Shub, eds., Springer, Berlin, 1997, pp. 216\u2013230.","DOI":"10.1007\/978-3-642-60539-0_16"},{"key":"R24","unstructured":"V. R\u00f6dl, unpublished."},{"key":"R25","unstructured":"E.\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":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797328847"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080730160","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:23:35Z","timestamp":1787322215000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080730160"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080730160"],"URL":"https:\/\/doi.org\/10.1137\/080730160","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}