Publication Information

{'id': 'https://openalex.org/W2963363569', 'doi': 'https://doi.org/10.1017/s096354831800024x', 'title': 'Fast Property Testing and Metrics for Permutations', 'display_name': 'Fast Property Testing and Metrics for Permutations', 'publication_year': 2018, 'publication_date': '2018-05-24', 'ids': {'openalex': 'https://openalex.org/W2963363569', 'doi': 'https://doi.org/10.1017/s096354831800024x', 'mag': '2963363569'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1017/s096354831800024x', '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': ['crossref'], 'open_access': {'is_oa': True, 'oa_status': 'green', 'oa_url': 'http://arxiv.org/pdf/1611.01270', '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': 'last', 'author': {'id': 'https://openalex.org/A5100911449', 'display_name': 'Fan Wei', 'orcid': None}, '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': 'FAN WEI', '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']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 1, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 1.036, 'has_fulltext': False, 'cited_by_count': 10, 'citation_normalized_percentile': {'value': 0.708412, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 85, 'max': 86}, 'biblio': {'volume': '27', 'issue': '4', 'first_page': '539', 'last_page': '579'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9995, '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.9995, '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/T12541', 'display_name': 'Graph Labeling and Dimension Problems', '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.9991, '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/property-testing', 'display_name': 'Property testing', 'score': 0.93492687}, {'id': 'https://openalex.org/keywords/constant', 'display_name': 'Constant (computer programming)', 'score': 0.54831475}], 'concepts': [{'id': 'https://openalex.org/C123842658', 'wikidata': 'https://www.wikidata.org/wiki/Q2918980', 'display_name': 'Property testing', 'level': 2, 'score': 0.93492687}, {'id': 'https://openalex.org/C189950617', 'wikidata': 'https://www.wikidata.org/wiki/Q937228', 'display_name': 'Property (philosophy)', 'level': 2, 'score': 0.82444525}, {'id': 'https://openalex.org/C176217482', 'wikidata': 'https://www.wikidata.org/wiki/Q860554', 'display_name': 'Metric (unit)', 'level': 2, 'score': 0.6325309}, {'id': 'https://openalex.org/C21308566', 'wikidata': 'https://www.wikidata.org/wiki/Q7169365', 'display_name': 'Permutation (music)', 'level': 2, 'score': 0.62419957}, {'id': 'https://openalex.org/C77553402', 'wikidata': 'https://www.wikidata.org/wiki/Q13222579', 'display_name': 'Upper and lower bounds', 'level': 2, 'score': 0.56562984}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.5595413}, {'id': 'https://openalex.org/C2777027219', 'wikidata': 'https://www.wikidata.org/wiki/Q1284190', 'display_name': 'Constant (computer programming)', 'level': 2, 'score': 0.54831475}, {'id': 'https://openalex.org/C311688', 'wikidata': 'https://www.wikidata.org/wiki/Q2393193', 'display_name': 'Time complexity', 'level': 2, 'score': 0.52857953}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.4337107}, {'id': 'https://openalex.org/C2781238097', 'wikidata': 'https://www.wikidata.org/wiki/Q175026', 'display_name': 'Object (grammar)', 'level': 2, 'score': 0.41005847}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.37538016}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.32997257}, {'id': 'https://openalex.org/C154945302', 'wikidata': 'https://www.wikidata.org/wiki/Q11660', 'display_name': 'Artificial intelligence', 'level': 1, 'score': 0.061316043}, {'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/C138885662', 'wikidata': 'https://www.wikidata.org/wiki/Q5891', 'display_name': 'Philosophy', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C21547014', 'wikidata': 'https://www.wikidata.org/wiki/Q1423657', 'display_name': 'Operations management', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C121332964', 'wikidata': 'https://www.wikidata.org/wiki/Q413', 'display_name': 'Physics', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C111472728', 'wikidata': 'https://www.wikidata.org/wiki/Q9471', 'display_name': 'Epistemology', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C24890656', 'wikidata': 'https://www.wikidata.org/wiki/Q82811', 'display_name': 'Acoustics', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C162324750', 'wikidata': 'https://www.wikidata.org/wiki/Q8134', 'display_name': 'Economics', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 2, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1017/s096354831800024x', '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': 'http://arxiv.org/abs/1611.01270', 'pdf_url': 'http://arxiv.org/pdf/1611.01270', '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}], 'best_oa_location': {'is_oa': True, 'landing_page_url': 'http://arxiv.org/abs/1611.01270', 'pdf_url': 'http://arxiv.org/pdf/1611.01270', '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': [], 'referenced_works_count': 30, 'referenced_works': ['https://openalex.org/W1487872891', 'https://openalex.org/W1515964912', 'https://openalex.org/W1596709027', 'https://openalex.org/W1600537614', 'https://openalex.org/W1691611448', 'https://openalex.org/W1926319616', 'https://openalex.org/W1927582220', 'https://openalex.org/W1970630090', 'https://openalex.org/W1972423218', 'https://openalex.org/W1985538939', 'https://openalex.org/W1986644892', 'https://openalex.org/W2007052372', 'https://openalex.org/W2018925011', 'https://openalex.org/W2037022974', 'https://openalex.org/W2043057332', 'https://openalex.org/W2069367490', 'https://openalex.org/W2091015960', 'https://openalex.org/W2092086436', 'https://openalex.org/W2139374679', 'https://openalex.org/W2141370238', 'https://openalex.org/W2141765721', 'https://openalex.org/W2143668817', 'https://openalex.org/W2144475416', 'https://openalex.org/W2161620758', 'https://openalex.org/W2405333517', 'https://openalex.org/W273178449', 'https://openalex.org/W2763468056', 'https://openalex.org/W2963005178', 'https://openalex.org/W3100333345', 'https://openalex.org/W4255609236'], 'related_works': ['https://openalex.org/W4289285543', 'https://openalex.org/W2980711752', 'https://openalex.org/W2963363569', 'https://openalex.org/W2950208222', 'https://openalex.org/W2901609193', 'https://openalex.org/W2568243855', 'https://openalex.org/W2551865055', 'https://openalex.org/W2318718798', 'https://openalex.org/W2263079341', 'https://openalex.org/W1996947585'], 'abstract_inverted_index': {'The': [0, 65], 'goal': [1], 'of': [2, 38, 60, 124, 161], 'property': [3, 14], 'testing': [4, 95, 121, 173], 'is': [5, 77, 105], 'to': [6, 98, 137, 165, 176], 'quickly': [7], 'distinguish': [8], 'between': [9], 'objects': [10, 16, 40], 'which': [11, 33, 142], 'satisfy': [12], 'a': [13, 84, 106, 131, 138], 'and': [15, 52, 55, 80], 'that': [17, 35, 156], 'are': [18, 25, 163], 'ε-far': [19], 'from': [20, 73], 'satisfying': [21], 'the': [22, 53, 58, 61, 69, 74, 99, 111, 146, 151, 166], 'property.': [23, 152], 'There': [24], 'now': [26], 'several': [27, 157], 'general': [28], 'results': [29, 171], 'in': [30, 114], 'this': [31], 'area': [32], 'show': [34, 155], 'natural': [36], 'properties': [37, 123], 'combinatorial': [39], 'can': [41], 'be': [42], 'tested': [43], 'with': [44, 96, 135, 174], '‘constant’': [45], 'query': [46, 70, 116], 'complexity,': [47], 'depending': [48, 109], 'only': [49], 'on': [50, 57, 68, 110, 145], 'ε': [51], 'property,': [54], 'not': [56], 'size': [59], 'object': [62], 'being': [63], 'tested.': [64], 'upper': [66], 'bound': [67, 118, 134], 'complexity': [71, 117], 'coming': [72], 'proof': [75], 'techniques': [76], 'often': [78], 'enormous': [79], 'impractical.': [81], 'It': [82], 'remains': [83], 'major': [85], 'open': [86], 'problem': [87], 'if': [88], 'better': [89], 'bounds': [90], 'hold.': [91], 'Maybe': [92], 'surprisingly,': [93], 'for': [94, 119, 150, 172], 'respect': [97, 136, 175], 'rectangular': [100, 167], 'distance,': [101, 168], 'we': [102, 154], 'prove': [103], 'there': [104], 'universal': [107], '(not': [108], 'property),': [112], 'polynomial': [113], '1/ε': [115], 'two-sided': [120], 'hereditary': [122], 'sufficiently': [125], 'large': [126], 'permutations.': [127], 'We': [128], 'further': [129], 'give': [130], 'nearly': [132], 'linear': [133], 'closely': [139], 'related': [140, 164], 'metric': [141], 'also': [143], 'depends': [144], 'smallest': [147], 'forbidden': [148], 'subpermutation': [149], 'Finally,': [153], 'different': [158], 'permutation': [159], 'metrics': [160], 'interest': [162], 'yielding': [169], 'similar': [170], 'these': [177], 'metrics.': [178]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2963363569', 'counts_by_year': [{'year': 2024, 'cited_by_count': 4}, {'year': 2021, 'cited_by_count': 3}, {'year': 2020, 'cited_by_count': 1}, {'year': 2019, 'cited_by_count': 2}], 'updated_date': '2024-12-11T19:42:56.281564', 'created_date': '2019-07-30'}