{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T16:46:19Z","timestamp":1725381979189},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T00:00:00Z","timestamp":1556841600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We provide a deterministic algorithm that finds, in \u025b<jats:sup>-<jats:italic>O<\/jats:italic>(1)<\/jats:sup><jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup> time, an \u025b-regular Frieze\u2013Kannan partition of a graph on <jats:italic>n<\/jats:italic> vertices. The algorithm outputs an approximation of a given graph as a weighted sum of \u025b<jats:sup>-<jats:italic>O<\/jats:italic>(1)<\/jats:sup> many complete bipartite graphs.<\/jats:p><jats:p>As a corollary, we give a deterministic algorithm for estimating the number of copies of <jats:italic>H<\/jats:italic> in an n-vertex graph <jats:italic>G<\/jats:italic> up to an additive error of at most <jats:italic>\u025bn<\/jats:italic><jats:sup><jats:italic>v(H)<\/jats:italic><\/jats:sup>, in time \u025b<jats:sup>-<jats:italic>O<\/jats:italic><jats:sub>H<\/jats:sub>(1)<\/jats:sup><jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>.<\/jats:p>","DOI":"10.1017\/s0963548319000075","type":"journal-article","created":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T08:28:47Z","timestamp":1556872127000},"page":"777-790","source":"Crossref","is-referenced-by-count":1,"title":["A fast new algorithm for weak graph regularity"],"prefix":"10.1017","volume":"28","author":[{"given":"Jacob","family":"Fox","sequence":"first","affiliation":[]},{"given":"L\u00e1szl\u00f3 Mikl\u00f3s","family":"Lov\u00e1sz","sequence":"additional","affiliation":[]},{"given":"Yufei","family":"Zhao","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,5,3]]},"reference":[{"key":"S0963548319000075_ref1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"S0963548319000075_ref10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408223"},{"key":"S0963548319000075_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"S0963548319000075_ref14","first-page":"51","article-title":"Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators","volume":"24","author":"Margulis","year":"1988","journal-title":"Problemy Peredachi Informatsii"},{"key":"S0963548319000075_ref18","unstructured":"[18] Szemer\u00e9di, E. (1978) Regular partitions of graphs. Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, Vol. 260, CNRS, Paris, pp. 399\u2013401."},{"key":"S0963548319000075_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"S0963548319000075_ref2","doi-asserted-by":"publisher","DOI":"10.1137\/110846373"},{"key":"S0963548319000075_ref13","first-page":"71","article-title":"Explicit constructions of expanders","volume":"9","author":"Margulis","year":"1973","journal-title":"Problemy Pereda\u010di Informacii"},{"key":"S0963548319000075_ref15","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1054"},{"key":"S0963548319000075_ref17","doi-asserted-by":"publisher","DOI":"10.4064\/aa-27-1-199-245"},{"key":"S0963548319000075_ref16","doi-asserted-by":"publisher","DOI":"10.2307\/3062153"},{"key":"S0963548319000075_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000200"},{"key":"S0963548319000075_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793247634"},{"key":"S0963548319000075_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000111"},{"key":"S0963548319000075_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000049"},{"key":"S0963548319000075_ref7","first-page":"12","volume-title":"37th Annual Symposium on Foundations of Computer Science","author":"Frieze","year":"1996"},{"key":"S0963548319000075_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"S0963548319000075_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0599-6"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T07:51:11Z","timestamp":1568188271000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000075\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,3]]},"references-count":18,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["S0963548319000075"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000075","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,3]]}}}