Publication Information

{'id': 'https://openalex.org/W2799781558', 'doi': None, 'title': 'Regularity and removal lemmas and their applications', 'display_name': 'Regularity and removal lemmas and their applications', 'publication_year': 2017, 'publication_date': '2017-01-01', 'ids': {'openalex': 'https://openalex.org/W2799781558', 'mag': '2799781558'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://dspace.mit.edu/handle/1721.1/112899', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'dissertation', 'type_crossref': 'dissertation', 'indexed_in': [], 'open_access': {'is_oa': False, 'oa_status': 'closed', 'oa_url': None, 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5067889485', 'display_name': 'László Lovász', 'orcid': 'https://orcid.org/0000-0002-6242-5894'}, 'institutions': [], 'countries': [], 'is_corresponding': True, 'raw_author_name': 'László Miklós Lovász', 'raw_affiliation_strings': [], 'affiliations': []}], 'institution_assertions': [], 'countries_distinct_count': 0, 'institutions_distinct_count': 0, 'corresponding_author_ids': ['https://openalex.org/A5067889485'], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': None, 'has_fulltext': False, 'cited_by_count': 0, 'citation_normalized_percentile': {'value': 0.0, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 0, 'max': 63}, 'biblio': {'volume': None, 'issue': None, 'first_page': None, 'last_page': None}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'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'}}, 'topics': [{'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'}}, {'id': 'https://openalex.org/T10374', 'display_name': 'Advanced Graph Theory Research', 'score': 0.9993, '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'}}], 'keywords': [{'id': 'https://openalex.org/keywords/lemma', 'display_name': 'Lemma (botany)', 'score': 0.8269867}], 'concepts': [{'id': 'https://openalex.org/C2777759810', 'wikidata': 'https://www.wikidata.org/wiki/Q149316', 'display_name': 'Lemma (botany)', 'level': 3, 'score': 0.8269867}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.8150438}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.6271514}, {'id': 'https://openalex.org/C77553402', 'wikidata': 'https://www.wikidata.org/wiki/Q13222579', 'display_name': 'Upper and lower bounds', 'level': 2, 'score': 0.57697284}, {'id': 'https://openalex.org/C42812', 'wikidata': 'https://www.wikidata.org/wiki/Q1082910', 'display_name': 'Partition (number theory)', 'level': 2, 'score': 0.5712818}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.52511936}, {'id': 'https://openalex.org/C80899671', 'wikidata': 'https://www.wikidata.org/wiki/Q1304193', 'display_name': 'Vertex (graph theory)', 'level': 3, 'score': 0.50968933}, {'id': 'https://openalex.org/C148764684', 'wikidata': 'https://www.wikidata.org/wiki/Q621751', 'display_name': 'Approximation algorithm', 'level': 2, 'score': 0.422191}, {'id': 'https://openalex.org/C2777831296', 'wikidata': 'https://www.wikidata.org/wiki/Q12518', 'display_name': 'Tower', 'level': 2, 'score': 0.41390556}, {'id': 'https://openalex.org/C132525143', 'wikidata': 'https://www.wikidata.org/wiki/Q141488', 'display_name': 'Graph', 'level': 2, 'score': 0.2750242}, {'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/C18903297', 'wikidata': 'https://www.wikidata.org/wiki/Q7150', 'display_name': 'Ecology', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C147176958', 'wikidata': 'https://www.wikidata.org/wiki/Q77590', 'display_name': 'Civil engineering', '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/C127413603', 'wikidata': 'https://www.wikidata.org/wiki/Q11023', 'display_name': 'Engineering', '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': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://dspace.mit.edu/handle/1721.1/112899', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}], 'best_oa_location': None, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 24, 'referenced_works': ['https://openalex.org/W1482513610', 'https://openalex.org/W1970630090', 'https://openalex.org/W1980424184', 'https://openalex.org/W1985538939', 'https://openalex.org/W1997230618', 'https://openalex.org/W2012026677', 'https://openalex.org/W2018925011', 'https://openalex.org/W2036871172', 'https://openalex.org/W2048958388', 'https://openalex.org/W2052318581', 'https://openalex.org/W2072858942', 'https://openalex.org/W2090798615', 'https://openalex.org/W2092086436', 'https://openalex.org/W2095273580', 'https://openalex.org/W2103012681', 'https://openalex.org/W2111754130', 'https://openalex.org/W2120248756', 'https://openalex.org/W2124366921', 'https://openalex.org/W2144475416', 'https://openalex.org/W2161620758', 'https://openalex.org/W2169968099', 'https://openalex.org/W2405333517', 'https://openalex.org/W273178449', 'https://openalex.org/W3023108254'], 'related_works': ['https://openalex.org/W912003938', 'https://openalex.org/W3168772390', 'https://openalex.org/W3107148815', 'https://openalex.org/W2984418642', 'https://openalex.org/W2952685556', 'https://openalex.org/W2952337821', 'https://openalex.org/W281488709', 'https://openalex.org/W2794535202', 'https://openalex.org/W2735923117', 'https://openalex.org/W2531891315', 'https://openalex.org/W2405333517', 'https://openalex.org/W2290305099', 'https://openalex.org/W2159703794', 'https://openalex.org/W2159063988', 'https://openalex.org/W2156482443', 'https://openalex.org/W2152535969', 'https://openalex.org/W2044011276', 'https://openalex.org/W2020236981', 'https://openalex.org/W1691611448', 'https://openalex.org/W1583576464'], 'abstract_inverted_index': {'In': [0], 'this': [1, 77], 'thesis,': [2], 'we': [3, 21, 58, 101, 167, 241], 'analyze': [4], 'the': [5, 17, 27, 39, 42, 93, 110, 128, 133, 170, 194, 198, 252, 256], 'regularity': [6, 68, 134, 176], 'method\npioneered': [7], 'by': [8], 'Szemeredi,': [9], 'and': [10, 178], 'also': [11, 108, 141], 'discuss': [12], 'one': [13], 'of': [14, 29, 35, 41, 92, 112, 135, 138, 196, 246, 258], 'its': [15], 'prevalent\napplications,': [16], 'removal': [18, 204, 236], 'lemma.': [19, 185], 'First,': [20], 'prove': [22, 182], 'a': [23, 33, 49, 54, 64, 80, 105, 136, 210, 221, 243], 'new': [24, 244], 'lower': [25], 'bound\non': [26], 'number': [28, 257], 'parts': [30, 156, 259], 'required': [31], 'in': [32, 45, 207, 238], 'version': [34], "Szemeredi's\nregularity": [36], 'lemma,': [37, 116, 177, 205], 'determining': [38], 'order': [40], 'tower': [43, 223], 'height': [44], 'that\nversion': [46], 'up': [47], 'to': [48, 60, 78, 104, 126, 131, 144, 169, 181, 260], 'constant': [50], 'factor.': [51], 'This': [52], 'addresses': [53], 'question': [55], 'of\nGowers.': [56], 'Next,': [57], 'turn': [59, 168], 'algorithms.': [61], 'We': [62, 75, 107, 123, 140, 225], 'give': [63, 79, 242], 'fast': [65], 'algorithmic\nFrieze-Kannan': [66], '(weak)': [67], 'lemma': [69, 130, 237, 248], 'that': [70], 'improves': [71], 'on': [72, 201, 255], 'previous\nrunning': [73], 'times.': [74], 'use': [76, 127], 'substantially': [81], 'faster\ndeterministic': [82], 'approximation': [83, 118], 'algorithm': [84], 'for': [85, 120, 147, 233, 249], 'counting': [86], 'subgraphs.\nPreviously,': [87], 'only': [88], 'an': [89, 114, 151, 159, 183, 229, 261], 'exponential': [90], 'dependence': [91], 'running': [94], 'time': [95], 'on\nthe': [96], 'error': [97], 'parameter': [98], 'was': [99], 'known;': [100], 'improve': [102], 'it': [103, 180], 'polynomial\ndependence.': [106], 'revisit': [109], 'problem': [111, 195], 'finding': [113], 'algorithmic\nregularity': [115], 'giving': [117], 'algorithms': [119], 'some\nco-NP-complete': [121], 'problems.': [122], 'show': [124, 142], 'how': [125, 143], 'Frieze-Kannan\nregularity': [129], 'approximate': [132], 'pair': [137], 'vertex\nsets.': [139], 'quickly': [145], 'find,': [146], 'each': [148], "[epsilon]'": [149], '>\n[epsilon],': [150], "[epsilon]'-regular": [152], 'partition': [153, 161], 'with': [154, 162, 220], 'k': [155, 163], 'if': [157], 'there\nexists': [158], '[epsilon]-regular': [160], 'parts.': [164], 'After': [165], 'studying\nalgorithms,': [166], 'arithmetic': [171], 'setting.': [172], 'Green': [173], 'proved': [174], 'an\narithmetic': [175], 'used': [179], 'arithmetic\nremoval': [184], 'The': [186, 214], 'bounds': [187, 200], 'obtained,': [188], 'however,': [189], 'were': [190], 'tower-type,': [191], 'and\nGreen': [192], 'posed': [193], 'improving': [197, 251], 'quantitative': [199], 'the\narithmetic': [202], 'triangle': [203], 'and,': [206], 'particular,': [208], 'asked\nwhether': [209], 'polynomial': [211], 'bound': [212, 218, 232, 254], 'holds.': [213], 'previous': [215], 'best': [216], 'known': [217], 'was\ntower-type': [219], 'logarithmic': [222], 'height.': [224], 'solve': [226], "Green's\nproblem,": [227], 'proving': [228], 'essentially': [230], 'tight': [231], "Green's": [234], 'arithmetic\ntriangle': [235], 'Fn/p.': [239], 'Finally,': [240], 'proof': [245], 'a\nregularity': [247], 'permutations,': [250], 'previous\ntower-type': [253], 'exponential\nbound.': [262]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2799781558', 'counts_by_year': [], 'updated_date': '2024-12-06T18:52:59.979598', 'created_date': '2018-05-17'}