Every monotone graph property is testable

Name: Work Video:
Duration: 3 min 30 s
Noga Alon; A. Shapira
{'id': 'https://openalex.org/W1980424184', 'doi': 'https://doi.org/10.1145/1060590.1060611', 'title': 'Every monotone graph property is testable', 'display_name': 'Every monotone graph property is testable', 'publication_year': 2005, 'publication_date': '2005-05-22', 'ids': {'openalex': 'https://openalex.org/W1980424184', 'doi': 'https://doi.org/10.1145/1060590.1060611', 'mag': '1980424184'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/1060590.1060611', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'proceedings-article', 'indexed_in': ['crossref'], 'open_access': {'is_oa': True, 'oa_status': 'green', 'oa_url': 'http://www.math.tau.ac.il/~nogaa/PDFS/monotone1.pdf', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5083469386', 'display_name': 'Noga Alon', 'orcid': 'https://orcid.org/0000-0003-1332-4883'}, 'institutions': [{'id': 'https://openalex.org/I16391192', 'display_name': 'Tel Aviv University', 'ror': 'https://ror.org/04mhzgx49', 'country_code': 'IL', 'type': 'education', 'lineage': ['https://openalex.org/I16391192']}], 'countries': ['IL'], 'is_corresponding': False, 'raw_author_name': 'Noga Alon', 'raw_affiliation_strings': ['Tel Aviv University, Tel Aviv, Isarel#TAB#'], 'affiliations': [{'raw_affiliation_string': 'Tel Aviv University, Tel Aviv, Isarel#TAB#', 'institution_ids': ['https://openalex.org/I16391192']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5089978763', 'display_name': 'A. Shapira', 'orcid': 'https://orcid.org/0000-0001-9902-0164'}, 'institutions': [{'id': 'https://openalex.org/I16391192', 'display_name': 'Tel Aviv University', 'ror': 'https://ror.org/04mhzgx49', 'country_code': 'IL', 'type': 'education', 'lineage': ['https://openalex.org/I16391192']}], 'countries': ['IL'], 'is_corresponding': False, 'raw_author_name': 'Asaf Shapira', 'raw_affiliation_strings': ['Tel Aviv University, Tel Aviv, Isarel#TAB#'], 'affiliations': [{'raw_affiliation_string': 'Tel Aviv University, Tel Aviv, Isarel#TAB#', 'institution_ids': ['https://openalex.org/I16391192']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 1, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 11.135, 'has_fulltext': True, 'fulltext_origin': 'ngrams', 'cited_by_count': 84, 'citation_normalized_percentile': {'value': 0.939404, 'is_in_top_1_percent': False, 'is_in_top_10_percent': True}, 'cited_by_percentile_year': {'min': 95, 'max': 96}, '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/T10374', 'display_name': 'Advanced Graph Theory Research', 'score': 0.9992, '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.9972, '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/graph-property', 'display_name': 'Graph property', 'score': 0.7574625}, {'id': 'https://openalex.org/keywords/null-graph', 'display_name': 'Null graph', 'score': 0.54725707}, {'id': 'https://openalex.org/keywords/complement-graph', 'display_name': 'Complement graph', 'score': 0.51465356}, {'id': 'https://openalex.org/keywords/property-testing', 'display_name': 'Property testing', 'score': 0.50859964}, {'id': 'https://openalex.org/keywords/critical-graph', 'display_name': 'Critical graph', 'score': 0.43630585}], 'concepts': [{'id': 'https://openalex.org/C64339825', 'wikidata': 'https://www.wikidata.org/wiki/Q722659', 'display_name': 'Graph property', 'level': 5, 'score': 0.7574625}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.61720085}, {'id': 'https://openalex.org/C203776342', 'wikidata': 'https://www.wikidata.org/wiki/Q1378376', 'display_name': 'Line graph', 'level': 3, 'score': 0.5613449}, {'id': 'https://openalex.org/C2834757', 'wikidata': 'https://www.wikidata.org/wiki/Q4925424', 'display_name': 'Monotone polygon', 'level': 2, 'score': 0.55750465}, {'id': 'https://openalex.org/C17169500', 'wikidata': 'https://www.wikidata.org/wiki/Q3033506', 'display_name': 'Null graph', 'level': 5, 'score': 0.54725707}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.54255486}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.5414271}, {'id': 'https://openalex.org/C168291704', 'wikidata': 'https://www.wikidata.org/wiki/Q902252', 'display_name': 'Complement graph', 'level': 5, 'score': 0.51465356}, {'id': 'https://openalex.org/C123842658', 'wikidata': 'https://www.wikidata.org/wiki/Q2918980', 'display_name': 'Property testing', 'level': 2, 'score': 0.50859964}, {'id': 'https://openalex.org/C22149727', 'wikidata': 'https://www.wikidata.org/wiki/Q7940747', 'display_name': 'Voltage graph', 'level': 4, 'score': 0.48782495}, {'id': 'https://openalex.org/C19332903', 'wikidata': 'https://www.wikidata.org/wiki/Q7623247', 'display_name': 'Strength of a graph', 'level': 5, 'score': 0.4782083}, {'id': 'https://openalex.org/C132525143', 'wikidata': 'https://www.wikidata.org/wiki/Q141488', 'display_name': 'Graph', 'level': 2, 'score': 0.46592686}, {'id': 'https://openalex.org/C167750561', 'wikidata': 'https://www.wikidata.org/wiki/Q1789512', 'display_name': 'Critical graph', 'level': 5, 'score': 0.43630585}, {'id': 'https://openalex.org/C2524010', 'wikidata': 'https://www.wikidata.org/wiki/Q8087', 'display_name': 'Geometry', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 2, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/1060590.1060611', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.2303', 'pdf_url': 'http://www.math.tau.ac.il/~nogaa/PDFS/monotone1.pdf', 'source': {'id': 'https://openalex.org/S4306400349', 'display_name': 'CiteSeer X (The Pennsylvania State University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I130769515', 'host_organization_name': 'Pennsylvania State University', 'host_organization_lineage': ['https://openalex.org/I130769515'], 'host_organization_lineage_names': ['Pennsylvania State University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}], 'best_oa_location': {'is_oa': True, 'landing_page_url': 'http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.2303', 'pdf_url': 'http://www.math.tau.ac.il/~nogaa/PDFS/monotone1.pdf', 'source': {'id': 'https://openalex.org/S4306400349', 'display_name': 'CiteSeer X (The Pennsylvania State University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I130769515', 'host_organization_name': 'Pennsylvania State University', 'host_organization_lineage': ['https://openalex.org/I130769515'], 'host_organization_lineage_names': ['Pennsylvania State University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, 'sustainable_development_goals': [{'score': 0.41, 'id': 'https://metadata.un.org/sdg/16', 'display_name': 'Peace, justice, and strong institutions'}], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 41, 'referenced_works': ['https://openalex.org/W100273703', 'https://openalex.org/W104148001', 'https://openalex.org/W1494854198', 'https://openalex.org/W1529556207', 'https://openalex.org/W1551595104', 'https://openalex.org/W1606712848', 'https://openalex.org/W1909155726', 'https://openalex.org/W1963993969', 'https://openalex.org/W1970630090', 'https://openalex.org/W1993525660', 'https://openalex.org/W1994434808', 'https://openalex.org/W1995043396', 'https://openalex.org/W2000079459', 'https://openalex.org/W2004294976', 'https://openalex.org/W2018925011', 'https://openalex.org/W2020551595', 'https://openalex.org/W2026244324', 'https://openalex.org/W2036501955', 'https://openalex.org/W2043632298', 'https://openalex.org/W2046124559', 'https://openalex.org/W2068871408', 'https://openalex.org/W2069816168', 'https://openalex.org/W2072500969', 'https://openalex.org/W2072808987', 'https://openalex.org/W2078289947', 'https://openalex.org/W2082435079', 'https://openalex.org/W2083580384', 'https://openalex.org/W2090798615', 'https://openalex.org/W2093276208', 'https://openalex.org/W2113140785', 'https://openalex.org/W2116537669', 'https://openalex.org/W2118212166', 'https://openalex.org/W2139374679', 'https://openalex.org/W2147588640', 'https://openalex.org/W2151906985', 'https://openalex.org/W2161620758', 'https://openalex.org/W2496163386', 'https://openalex.org/W2798428635', 'https://openalex.org/W2911327865', 'https://openalex.org/W2913941596', 'https://openalex.org/W3008660429'], 'related_works': ['https://openalex.org/W621782861', 'https://openalex.org/W3091695494', 'https://openalex.org/W2398840648', 'https://openalex.org/W2171582965', 'https://openalex.org/W2156516121', 'https://openalex.org/W2076599430', 'https://openalex.org/W2016987856', 'https://openalex.org/W1980424184', 'https://openalex.org/W1970630090', 'https://openalex.org/W1968752573'], 'abstract_inverted_index': {'A': [0], 'graph': [1, 30, 40, 49, 65, 100, 139, 145, 159, 181, 205, 209, 240, 251], 'property': [2, 66, 91, 146, 162, 206], 'is': [3, 8, 20, 61, 116, 173, 200, 211, 242, 256], 'called': [4], 'monotone': [5, 29, 48, 64, 204], 'if': [6, 18], 'it': [7, 19, 255], 'closed': [9, 21], 'under': [10, 22], 'taking': [11], '(not': [12], 'necessarily': [13], 'induced)': [14], 'subgraphs': [15], '(or,': [16], 'equivalently,': [17], 'removal': [23], 'of': [24, 34, 46, 90, 98, 113, 119, 122, 150, 166, 170, 178, 220, 250, 265], 'edges': [25], 'and': [26, 42, 73, 93, 141, 161], 'vertices).': [27], 'Many': [28], 'properties': [31, 38, 50, 101, 182, 252], 'are': [32, 165], 'some': [33], 'the': [35, 43, 88, 96, 111, 114, 175, 234, 266], 'most': [36], 'well-studied': [37, 99], 'in': [39, 58, 87, 135, 142, 158, 197], 'theory,': [41], 'abstract': [44], 'family': [45], 'all': [47, 137], 'was': [51], 'also': [52, 94, 154], 'extensively': [53], 'studied.': [54], 'Our': [55], 'main': [56, 127], 'result': [57, 82], 'this': [59, 130], 'paper': [60], 'that': [62, 102, 174, 201, 210], 'any': [63, 203, 208], 'can': [67], 'be': [68, 108, 133, 187], 'tested': [69], 'with': [70, 74, 183], 'one-sided': [71, 184], 'error,': [72], 'query': [75, 176], 'complexity': [76, 177], 'depending': [77, 222], 'only': [78], 'on': [79, 223], 'ε.': [80], 'This': [81], 'unifies': [83], 'several': [84], 'previous': [85, 195], 'results': [86, 157, 172, 196], 'area': [89], 'testing,': [92, 163], 'implies': [95], 'testability': [97], 'were': [103], 'previously': [104], 'not': [105, 228], 'known': [106], 'to': [107], 'testable.': [109], 'At': [110], 'heart': [112], 'proof': [115], 'an': [117], 'application': [118, 131], 'a': [120, 148, 218, 239, 246], 'variant': [121], "Szemerédi's": [123], 'Regularity': [124], 'Lemma.': [125], 'The': [126], 'ideas': [128], 'behind': [129], 'may': [132, 186], 'useful': [134], 'characterizing': [136], 'testable': [138, 180], 'properties,': [140], 'generally': [143], 'studying': [144], 'testing.As': [147], 'byproduct': [149], 'our': [151], 'techniques': [152], 'we': [153, 232], 'obtain': [155], 'additional': [156], 'theory': [160], 'which': [164, 192, 226], 'independent': [167], 'interest.': [168], 'One': [169], 'these': [171], 'testing': [179], 'error': [185], 'arbitrarily': [188], 'large.': [189], 'Another': [190], 'result,': [191], 'significantly': [193], 'extends': [194], 'extremal': [198], 'graph-theory,': [199], 'for': [202], 'P,': [207, 216, 253], 'ε': [212, 224], '-far': [213], 'from': [214, 244, 262], 'satisfying': [215, 245, 263], 'contains': [217], 'subgraph': [219], 'size': [221], 'only,': [225], 'does': [227], 'satisfy': [229], 'P.': [230], 'Finally,': [231], 'prove': [233], 'following': [235], 'compactness': [236], 'statement:': [237], 'If': [238], 'G': [241], 'ε-far': [243, 261], '(possibly': [247], 'infinite)': [248], 'set': [249], 'then': [254], 'at': [257], 'least': [258], 'δ': [259], 'P': [260], 'one': [264], 'properties.': [267]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W1980424184', 'counts_by_year': [{'year': 2024, 'cited_by_count': 2}, {'year': 2023, 'cited_by_count': 1}, {'year': 2021, 'cited_by_count': 1}, {'year': 2020, 'cited_by_count': 3}, {'year': 2019, 'cited_by_count': 3}, {'year': 2017, 'cited_by_count': 2}, {'year': 2014, 'cited_by_count': 1}, {'year': 2012, 'cited_by_count': 6}], 'updated_date': '2024-12-07T20:09:25.914855', 'created_date': '2016-06-24'}
Publication Information

Basic Information

Access and Citation

AI Researcher Chatbot

Primary Location

Authors

Topics

Keywords

Related Works
