Publication Information

{'id': 'https://openalex.org/W2405333517', 'doi': 'https://doi.org/10.1017/s0963548317000049', 'title': 'On Regularity Lemmas and their Algorithmic Applications', 'display_name': 'On Regularity Lemmas and their Algorithmic Applications', 'publication_year': 2017, 'publication_date': '2017-03-28', 'ids': {'openalex': 'https://openalex.org/W2405333517', 'doi': 'https://doi.org/10.1017/s0963548317000049', 'mag': '2405333517'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1017/s0963548317000049', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S7291079', 'display_name': 'Combinatorics Probability Computing', 'issn_l': '0963-5483', 'issn': ['0963-5483', '1469-2163'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310311721', 'host_organization_name': 'Cambridge University Press', 'host_organization_lineage': ['https://openalex.org/P4310311721', 'https://openalex.org/P4310311702'], 'host_organization_lineage_names': ['Cambridge University Press', 'University of Cambridge'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'journal-article', 'indexed_in': ['arxiv', 'crossref', 'datacite'], 'open_access': {'is_oa': True, 'oa_status': 'green', 'oa_url': 'https://arxiv.org/pdf/1604.00733', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5112361944', 'display_name': 'Jacob Fox', 'orcid': 'https://orcid.org/0000-0002-0664-497X'}, 'institutions': [{'id': 'https://openalex.org/I97018004', 'display_name': 'Stanford University', 'ror': 'https://ror.org/00f54p054', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I97018004']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'JACOB FOX', 'raw_affiliation_strings': ['Department of Mathematics, Stanford University, Stanford, CA 94305, USA (e-mail:'], 'affiliations': [{'raw_affiliation_string': 'Department of Mathematics, Stanford University, Stanford, CA 94305, USA (e-mail:', 'institution_ids': ['https://openalex.org/I97018004']}]}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5067889485', 'display_name': 'László Lovász', 'orcid': 'https://orcid.org/0000-0002-6242-5894'}, 'institutions': [{'id': 'https://openalex.org/I63966007', 'display_name': 'Massachusetts Institute of Technology', 'ror': 'https://ror.org/042nb2s44', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I63966007']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'LÁSZLÓ MIKLÓS LOVÁSZ', 'raw_affiliation_strings': ['Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA (e-mail:'], 'affiliations': [{'raw_affiliation_string': 'Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA (e-mail:', 'institution_ids': ['https://openalex.org/I63966007']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5021133458', 'display_name': 'Yufei Zhao', 'orcid': 'https://orcid.org/0000-0002-1995-3755'}, 'institutions': [{'id': 'https://openalex.org/I40120149', 'display_name': 'University of Oxford', 'ror': 'https://ror.org/052gg0110', 'country_code': 'GB', 'type': 'education', 'lineage': ['https://openalex.org/I40120149']}], 'countries': ['GB'], 'is_corresponding': False, 'raw_author_name': 'YUFEI ZHAO', 'raw_affiliation_strings': ['Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK (e-mail:'], 'affiliations': [{'raw_affiliation_string': 'Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK (e-mail:', 'institution_ids': ['https://openalex.org/I40120149']}]}], 'institution_assertions': [], 'countries_distinct_count': 2, 'institutions_distinct_count': 3, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 3.662, 'has_fulltext': True, 'fulltext_origin': 'pdf', 'cited_by_count': 17, 'citation_normalized_percentile': {'value': 0.838859, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 89, 'max': 90}, 'biblio': {'volume': '26', 'issue': '4', 'first_page': '481', 'last_page': '505'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10374', 'display_name': 'Advanced Graph Theory Research', 'score': 0.9999, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, 'topics': [{'id': 'https://openalex.org/T10374', 'display_name': 'Advanced Graph Theory Research', 'score': 0.9999, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9999, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T11329', 'display_name': 'Limits and Structures in Graph Theory', 'score': 0.9999, 'subfield': {'id': 'https://openalex.org/subfields/2607', 'display_name': 'Discrete Mathematics and Combinatorics'}, 'field': {'id': 'https://openalex.org/fields/26', 'display_name': 'Mathematics'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/lemma', 'display_name': 'Lemma (botany)', 'score': 0.8464289}, {'id': 'https://openalex.org/keywords/bounding-overwatch', 'display_name': 'Bounding overwatch', 'score': 0.41317308}], 'concepts': [{'id': 'https://openalex.org/C2777759810', 'wikidata': 'https://www.wikidata.org/wiki/Q149316', 'display_name': 'Lemma (botany)', 'level': 3, 'score': 0.8464289}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.816826}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.6710602}, {'id': 'https://openalex.org/C108710211', 'wikidata': 'https://www.wikidata.org/wiki/Q11538', 'display_name': 'Mathematical proof', 'level': 2, 'score': 0.6560401}, {'id': 'https://openalex.org/C42812', 'wikidata': 'https://www.wikidata.org/wiki/Q1082910', 'display_name': 'Partition (number theory)', 'level': 2, 'score': 0.639388}, {'id': 'https://openalex.org/C80899671', 'wikidata': 'https://www.wikidata.org/wiki/Q1304193', 'display_name': 'Vertex (graph theory)', 'level': 3, 'score': 0.5637366}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.5589922}, {'id': 'https://openalex.org/C77553402', 'wikidata': 'https://www.wikidata.org/wiki/Q13222579', 'display_name': 'Upper and lower bounds', 'level': 2, 'score': 0.537026}, {'id': 'https://openalex.org/C63584917', 'wikidata': 'https://www.wikidata.org/wiki/Q333286', 'display_name': 'Bounding overwatch', 'level': 2, 'score': 0.41317308}, {'id': 'https://openalex.org/C132525143', 'wikidata': 'https://www.wikidata.org/wiki/Q141488', 'display_name': 'Graph', 'level': 2, 'score': 0.3729197}, {'id': 'https://openalex.org/C18903297', 'wikidata': 'https://www.wikidata.org/wiki/Q7150', 'display_name': 'Ecology', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C134306372', 'wikidata': 'https://www.wikidata.org/wiki/Q7754', 'display_name': 'Mathematical analysis', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C2524010', 'wikidata': 'https://www.wikidata.org/wiki/Q8087', 'display_name': 'Geometry', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C46757340', 'wikidata': 'https://www.wikidata.org/wiki/Q43238', 'display_name': 'Poaceae', 'level': 2, 'score': 0.0}, {'id': 'https://openalex.org/C154945302', 'wikidata': 'https://www.wikidata.org/wiki/Q11660', 'display_name': 'Artificial intelligence', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C86803240', 'wikidata': 'https://www.wikidata.org/wiki/Q420', 'display_name': 'Biology', 'level': 0, 'score': 0.0}], 'mesh': [], 'locations_count': 3, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1017/s0963548317000049', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S7291079', 'display_name': 'Combinatorics Probability Computing', 'issn_l': '0963-5483', 'issn': ['0963-5483', '1469-2163'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310311721', 'host_organization_name': 'Cambridge University Press', 'host_organization_lineage': ['https://openalex.org/P4310311721', 'https://openalex.org/P4310311702'], 'host_organization_lineage_names': ['Cambridge University Press', 'University of Cambridge'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/1604.00733', 'pdf_url': 'https://arxiv.org/pdf/1604.00733', 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://api.datacite.org/dois/10.48550/arxiv.1604.00733', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4393179698', 'display_name': 'DataCite API', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I4210145204', 'host_organization_name': 'DataCite', 'host_organization_lineage': ['https://openalex.org/I4210145204'], 'host_organization_lineage_names': ['DataCite'], 'type': 'metadata'}, 'license': None, 'license_id': None, 'version': None}], 'best_oa_location': {'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/1604.00733', 'pdf_url': 'https://arxiv.org/pdf/1604.00733', 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': ['https://openalex.org/W2405333517', 'https://openalex.org/W3100333345'], 'referenced_works_count': 32, 'referenced_works': ['https://openalex.org/W1691611448', 'https://openalex.org/W1780823682', 'https://openalex.org/W1960897633', 'https://openalex.org/W1979740015', 'https://openalex.org/W1997230618', 'https://openalex.org/W2004694806', 'https://openalex.org/W2019367452', 'https://openalex.org/W2052318581', 'https://openalex.org/W2068571612', 'https://openalex.org/W2068871408', 'https://openalex.org/W2072858942', 'https://openalex.org/W2081254453', 'https://openalex.org/W2083580384', 'https://openalex.org/W2092086436', 'https://openalex.org/W2111754130', 'https://openalex.org/W2120248756', 'https://openalex.org/W2124366921', 'https://openalex.org/W2126186592', 'https://openalex.org/W2128139967', 'https://openalex.org/W2141649469', 'https://openalex.org/W2141765721', 'https://openalex.org/W2160594140', 'https://openalex.org/W2293834400', 'https://openalex.org/W2401939847', 'https://openalex.org/W2405333517', 'https://openalex.org/W2610183793', 'https://openalex.org/W273178449', 'https://openalex.org/W2977322974', 'https://openalex.org/W3023108254', 'https://openalex.org/W3104055895', 'https://openalex.org/W648165475', 'https://openalex.org/W648608585'], 'related_works': ['https://openalex.org/W4254119641', 'https://openalex.org/W4221036368', 'https://openalex.org/W3196207352', 'https://openalex.org/W3084261076', 'https://openalex.org/W3006682748', 'https://openalex.org/W2963408011', 'https://openalex.org/W2951724202', 'https://openalex.org/W2576399385', 'https://openalex.org/W2044959892', 'https://openalex.org/W1998171255'], 'abstract_inverted_index': {"Szemerédi's": [0], 'regularity': [1, 24, 44, 70, 118, 135, 140, 181], 'lemma': [2, 45, 71, 136, 182], 'and': [3, 101], 'its': [4], 'variants': [5], 'are': [6], 'some': [7], 'of': [8, 55, 57, 66, 114, 141, 144, 178, 191], 'the': [9, 23, 35, 38, 43, 53, 58, 67, 92, 96, 112, 132, 139, 179, 185, 189, 194], 'most': [10], 'powerful': [11], 'tools': [12], 'in': [13, 42, 83, 193], 'combinatorics.': [14], 'In': [15], 'this': [16], 'paper,': [17], 'we': [18, 27, 33, 61, 102, 110, 173], 'establish': [19], 'several': [20, 124], 'results': [21], 'around': [22], 'lemma.': [25], 'First,': [26], 'prove': [28], 'that': [29, 37], 'whether': [30], 'or': [31], 'not': [32], 'include': [34], 'condition': [36], 'desired': [39], 'vertex': [40, 145], 'partition': [41, 159, 168], 'is': [46], 'equitable': [47], 'has': [48], 'a': [49, 74, 84, 106, 142, 175, 198], 'minimal': [50], 'effect': [51], 'on': [52, 95, 188], 'number': [54, 190], 'parts': [56, 162, 192], 'partition.': [59], 'Second,': [60], 'use': [62, 131], 'an': [63, 88, 116, 157, 166], 'algorithmic': [64, 117], 'version': [65], '(weak)': [68], 'Frieze–Kannan': [69, 134], 'to': [72, 105, 130, 137, 151, 197], 'give': [73, 174], 'substantially': [75], 'faster': [76], 'deterministic': [77], 'approximation': [78, 121], 'algorithm': [79], 'for': [80, 91, 123, 154], 'counting': [81], 'subgraphs': [82], 'graph.': [85], 'Previously,': [86], 'only': [87], 'exponential': [89, 200], 'dependence': [90], 'running': [93], 'time': [94], 'error': [97], 'parameter': [98], 'was': [99], 'known,': [100], 'improve': [103], 'it': [104], 'polynomial': [107], 'dependence.': [108], 'Third,': [109], 'revisit': [111], 'problem': [113], 'finding': [115], 'lemma,': [119], 'giving': [120], 'algorithms': [122], 'co-NP-complete': [125], 'problems.': [126], 'We': [127, 147], 'show': [128, 149], 'how': [129, 150], 'weak': [133], 'approximate': [138], 'pair': [143], 'subsets.': [146], 'also': [148], 'quickly': [152], 'find,': [153], 'each': [155], 'ε′>ε,': [156], 'ε′-regular': [158], 'with': [160, 169], 'k': [161, 170], 'if': [163], 'there': [164], 'exists': [165], 'ε-regular': [167], 'parts.': [171], 'Finally,': [172], 'simple': [176], 'proof': [177], 'permutation': [180], 'which': [183], 'improves': [184], 'tower-type': [186], 'bound': [187], 'previous': [195], 'proofs': [196], 'single': [199], 'bound.': [201]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2405333517', 'counts_by_year': [{'year': 2024, 'cited_by_count': 1}, {'year': 2020, 'cited_by_count': 5}, {'year': 2019, 'cited_by_count': 3}, {'year': 2018, 'cited_by_count': 3}, {'year': 2017, 'cited_by_count': 4}, {'year': 2016, 'cited_by_count': 1}], 'updated_date': '2025-01-04T15:26:31.547200', 'created_date': '2016-06-24'}