{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:23:02Z","timestamp":1759335782106},"reference-count":27,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2017,3,28]],"date-time":"2017-03-28T00:00:00Z","timestamp":1490659200000},"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":[[2017,7]]},"abstract":"<jats:p>Szemer\u00e9di's regularity lemma and its variants are some of the most powerful tools in combinatorics. In this paper, we establish several results around the regularity lemma. First, we prove that whether or not we include the condition that the desired vertex partition in the regularity lemma is equitable has a minimal effect on the number of parts of the partition. Second, we use an algorithmic version of the (weak) Frieze\u2013Kannan regularity lemma to give a substantially faster deterministic approximation algorithm for counting subgraphs in a graph. Previously, only an exponential dependence for the running time on the error parameter was known, and we improve it to a polynomial dependence. Third, we revisit the problem of finding an algorithmic regularity lemma, giving approximation algorithms for several co-NP-complete problems. We show how to use the weak Frieze\u2013Kannan regularity lemma to approximate the regularity of a pair of vertex subsets. We also show how to quickly find, for each \u03b5\u2032&gt;\u03b5, an \u03b5\u2032-regular partition with<jats:italic>k<\/jats:italic>parts if there exists an \u03b5-regular partition with<jats:italic>k<\/jats:italic>parts. Finally, we give a simple proof of the permutation regularity lemma which improves the tower-type bound on the number of parts in the previous proofs to a single exponential bound.<\/jats:p>","DOI":"10.1017\/s0963548317000049","type":"journal-article","created":{"date-parts":[[2017,3,28]],"date-time":"2017-03-28T09:42:56Z","timestamp":1490694176000},"page":"481-505","source":"Crossref","is-referenced-by-count":12,"title":["On Regularity Lemmas and their Algorithmic Applications"],"prefix":"10.1017","volume":"26","author":[{"given":"JACOB","family":"FOX","sequence":"first","affiliation":[]},{"given":"L\u00c1SZL\u00d3 MIKL\u00d3S","family":"LOV\u00c1SZ","sequence":"additional","affiliation":[]},{"given":"YUFEI","family":"ZHAO","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2017,3,28]]},"reference":[{"key":"S0963548317000049_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0599-6"},{"key":"S0963548317000049_ref18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408223"},{"key":"S0963548317000049_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"S0963548317000049_ref6","doi-asserted-by":"crossref","first-page":"22","DOI":"10.37236\/1048","article-title":"A permutation regularity lemma","volume":"13","author":"Cooper","year":"2006","journal-title":"Electron. J. Combin."},{"key":"S0963548317000049_ref26","volume-title":"An Epsilon of Room, II","author":"Tao","year":"2010"},{"key":"S0963548317000049_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.06.002"},{"key":"S0963548317000049_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001621"},{"key":"S0963548317000049_ref25","first-page":"399","volume-title":"Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes, Vol. 260 of Colloq. Internat. CNRS","author":"Szemer\u00e9di","year":"1978"},{"key":"S0963548317000049_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548317000049_ref12","unstructured":"Fox J. and Lov\u00e1sz L. M. A tight lower bound for Szemer\u00e9di's regularity lemma. Combinatorica, to appear."},{"key":"S0963548317000049_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.07.008"},{"key":"S0963548317000049_ref19","first-page":"295","volume-title":"Combinatorics: Paul Erd\u0151s is Eighty","author":"Koml\u00f3s","year":"1996"},{"key":"S0963548317000049_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-012-0171-x"},{"key":"S0963548317000049_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"S0963548317000049_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/080717584"},{"key":"S0963548317000049_ref14","doi-asserted-by":"crossref","first-page":"17","DOI":"10.37236\/1449","article-title":"A simple algorithm for constructing Szemer\u00e9di's regularity partition","volume":"6","author":"Frieze","year":"1999","journal-title":"Electron. J. Combin."},{"key":"S0963548317000049_ref20","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"S0963548317000049_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/110846373"},{"key":"S0963548317000049_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000200"},{"key":"S0963548317000049_ref24","first-page":"503","volume-title":"Proc. International Congress of Mathematicians 1974","author":"Szemer\u00e9di","year":"1975"},{"key":"S0963548317000049_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"S0963548317000049_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3166-4"},{"key":"S0963548317000049_ref27","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"},{"key":"S0963548317000049_ref10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793247634"},{"key":"S0963548317000049_ref1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"S0963548317000049_ref2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441629"},{"key":"S0963548317000049_ref21","volume-title":"Large Networks and Graph Limits, Vol. 60 of American Mathematical Society Colloquium Publications","author":"Lov\u00e1sz","year":"2012"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548317000049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,4]],"date-time":"2020-10-04T13:48:23Z","timestamp":1601819303000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548317000049\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,28]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["S0963548317000049"],"URL":"https:\/\/doi.org\/10.1017\/s0963548317000049","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,28]]}}}