Publication Information

{'id': 'https://openalex.org/W4242600797', 'doi': 'https://doi.org/10.1137/1.9781611974331.ch87', 'title': 'Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky', 'display_name': 'Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky', 'publication_year': 2015, 'publication_date': '2015-12-21', 'ids': {'openalex': 'https://openalex.org/W4242600797', 'doi': 'https://doi.org/10.1137/1.9781611974331.ch87'}, 'language': 'en', 'primary_location': {'is_oa': True, 'landing_page_url': 'https://doi.org/10.1137/1.9781611974331.ch87', 'pdf_url': 'https://epubs.siam.org/doi/pdf/10.1137/1.9781611974331.ch87', 'source': None, 'license': None, 'license_id': None, 'version': 'publishedVersion', 'is_accepted': True, 'is_published': True}, 'type': 'article', 'type_crossref': 'proceedings-article', 'indexed_in': ['crossref'], 'open_access': {'is_oa': True, 'oa_status': 'bronze', 'oa_url': 'https://epubs.siam.org/doi/pdf/10.1137/1.9781611974331.ch87', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5032955418', 'display_name': 'Timothy M. Chan', 'orcid': 'https://orcid.org/0000-0002-8093-0675'}, 'institutions': [{'id': 'https://openalex.org/I151746483', 'display_name': 'University of Waterloo', 'ror': 'https://ror.org/01aff2v68', 'country_code': 'CA', 'type': 'education', 'lineage': ['https://openalex.org/I151746483']}], 'countries': ['CA'], 'is_corresponding': True, 'raw_author_name': 'Timothy M. Chan', 'raw_affiliation_strings': ['Cheriton School of Computer Science, University of Waterloo,'], 'affiliations': [{'raw_affiliation_string': 'Cheriton School of Computer Science, University of Waterloo,', 'institution_ids': ['https://openalex.org/I151746483']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5063871533', 'display_name': 'Ryan Williams', 'orcid': 'https://orcid.org/0000-0003-2326-2233'}, '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': 'Ryan Williams', 'raw_affiliation_strings': ['Computer Science Department, Stanford University,'], 'affiliations': [{'raw_affiliation_string': 'Computer Science Department, Stanford University,', 'institution_ids': ['https://openalex.org/I97018004']}]}], 'institution_assertions': [], 'countries_distinct_count': 2, 'institutions_distinct_count': 2, 'corresponding_author_ids': ['https://openalex.org/A5032955418'], 'corresponding_institution_ids': ['https://openalex.org/I151746483'], 'apc_list': None, 'apc_paid': None, 'fwci': 2.056, 'has_fulltext': True, 'fulltext_origin': 'pdf', 'cited_by_count': 34, 'citation_normalized_percentile': {'value': 0.940426, 'is_in_top_1_percent': False, 'is_in_top_10_percent': True}, 'cited_by_percentile_year': {'min': 94, 'max': 95}, '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.9941, '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.9941, '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/T10948', 'display_name': 'Advanced Combinatorial Mathematics', 'score': 0.9939, '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/T12072', 'display_name': 'Machine Learning and Algorithms', 'score': 0.9908, 'subfield': {'id': 'https://openalex.org/subfields/1702', 'display_name': 'Artificial Intelligence'}, '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/satisfiability', 'display_name': 'Satisfiability', 'score': 0.68595356}, {'id': 'https://openalex.org/keywords/randomized-algorithm', 'display_name': 'Randomized Algorithm', 'score': 0.64547133}, {'id': 'https://openalex.org/keywords/deterministic-algorithm', 'display_name': 'Deterministic algorithm', 'score': 0.6144213}], 'concepts': [{'id': 'https://openalex.org/C168773769', 'wikidata': 'https://www.wikidata.org/wiki/Q1350299', 'display_name': 'Satisfiability', 'level': 2, 'score': 0.68595356}, {'id': 'https://openalex.org/C128669082', 'wikidata': 'https://www.wikidata.org/wiki/Q583461', 'display_name': 'Randomized algorithm', 'level': 2, 'score': 0.64547133}, {'id': 'https://openalex.org/C13533509', 'wikidata': 'https://www.wikidata.org/wiki/Q1064349', 'display_name': 'Deterministic algorithm', 'level': 2, 'score': 0.6144213}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.5841764}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.5323278}, {'id': 'https://openalex.org/C165064840', 'wikidata': 'https://www.wikidata.org/wiki/Q1321061', 'display_name': 'Matching (statistics)', 'level': 2, 'score': 0.51372373}, {'id': 'https://openalex.org/C3017489831', 'wikidata': 'https://www.wikidata.org/wiki/Q2393193', 'display_name': 'Running time', 'level': 2, 'score': 0.49181226}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.44260404}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.4149352}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.35046458}, {'id': 'https://openalex.org/C105795698', 'wikidata': 'https://www.wikidata.org/wiki/Q12483', 'display_name': 'Statistics', 'level': 1, 'score': 0.11723271}], 'mesh': [], 'locations_count': 2, 'locations': [{'is_oa': True, 'landing_page_url': 'https://doi.org/10.1137/1.9781611974331.ch87', 'pdf_url': 'https://epubs.siam.org/doi/pdf/10.1137/1.9781611974331.ch87', 'source': None, 'license': None, 'license_id': None, 'version': 'publishedVersion', 'is_accepted': True, 'is_published': True}, {'is_oa': True, 'landing_page_url': 'https://hdl.handle.net/1721.1/143937', 'pdf_url': 'https://dspace.mit.edu/bitstream/1721.1/143937/2/detapsp_soda.pdf', 'source': {'id': 'https://openalex.org/S4306400425', 'display_name': 'DSpace@MIT (Massachusetts Institute of Technology)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I63966007', 'host_organization_name': 'Massachusetts Institute of Technology', 'host_organization_lineage': ['https://openalex.org/I63966007'], 'host_organization_lineage_names': ['Massachusetts Institute of Technology'], 'type': 'repository'}, 'license': 'cc-by-nc-sa', 'license_id': 'https://openalex.org/licenses/cc-by-nc-sa', 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}], 'best_oa_location': {'is_oa': True, 'landing_page_url': 'https://doi.org/10.1137/1.9781611974331.ch87', 'pdf_url': 'https://epubs.siam.org/doi/pdf/10.1137/1.9781611974331.ch87', 'source': None, 'license': None, 'license_id': None, 'version': 'publishedVersion', 'is_accepted': True, 'is_published': True}, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 47, 'referenced_works': ['https://openalex.org/W1430582609', 'https://openalex.org/W1481393877', 'https://openalex.org/W1495935433', 'https://openalex.org/W1527197079', 'https://openalex.org/W1542191788', 'https://openalex.org/W1544195453', 'https://openalex.org/W1550435233', 'https://openalex.org/W1569200683', 'https://openalex.org/W1571792361', 'https://openalex.org/W1608550999', 'https://openalex.org/W1655990431', 'https://openalex.org/W1745272466', 'https://openalex.org/W1898653522', 'https://openalex.org/W1953176910', 'https://openalex.org/W1969865855', 'https://openalex.org/W1979124844', 'https://openalex.org/W1996980357', 'https://openalex.org/W2009994177', 'https://openalex.org/W2019807548', 'https://openalex.org/W2021227709', 'https://openalex.org/W2026339776', 'https://openalex.org/W2028341270', 'https://openalex.org/W2036350017', 'https://openalex.org/W2049153008', 'https://openalex.org/W2050715481', 'https://openalex.org/W2058426370', 'https://openalex.org/W2064790310', 'https://openalex.org/W2070678975', 'https://openalex.org/W2072064573', 'https://openalex.org/W2074359677', 'https://openalex.org/W2102477571', 'https://openalex.org/W2104734478', 'https://openalex.org/W2114365471', 'https://openalex.org/W2116794057', 'https://openalex.org/W2137407595', 'https://openalex.org/W2140232587', 'https://openalex.org/W2147154704', 'https://openalex.org/W2158695970', 'https://openalex.org/W2242296381', 'https://openalex.org/W2281885423', 'https://openalex.org/W2545919726', 'https://openalex.org/W2611287588', 'https://openalex.org/W2623873233', 'https://openalex.org/W3022326557', 'https://openalex.org/W4241657494', 'https://openalex.org/W4243032598', 'https://openalex.org/W4253255388'], 'related_works': ['https://openalex.org/W4387389933', 'https://openalex.org/W2565865680', 'https://openalex.org/W2526609438', 'https://openalex.org/W2261374484', 'https://openalex.org/W2174440985', 'https://openalex.org/W2112526268', 'https://openalex.org/W2053924317', 'https://openalex.org/W2011643166', 'https://openalex.org/W1964089073', 'https://openalex.org/W1508924483'], 'abstract_inverted_index': {'We': [0], 'show': [1], 'how': [2, 15], 'to': [3, 16, 60, 87, 118, 125, 132], 'solve': [4], 'all-pairs': [5], 'shortest': [6], 'paths': [7], 'on': [8, 92], 'n': [9, 24, 93], 'nodes': [10], 'in': [11, 27, 32, 96], 'deterministic': [12, 33, 75], 'time,': [13, 98], 'and': [14, 49, 52, 57, 109, 142], 'count': [17, 61, 89], 'the': [18, 41, 58, 101, 133], 'pairs': [19], 'of': [20, 46, 114, 135], 'orthogonal': [21], 'vectors': [22, 26], 'among': [23], '0–1': [25], 'd': [28], '=': [29], 'clogn': [30], 'dimensions': [31], 'n2–1/O(logc)': [34], 'time.': [35], 'These': [36], 'running': [37, 104], 'times': [38, 105], 'essentially': [39], 'match': [40], 'best': [42, 102], 'known': [43, 103], 'randomized': [44, 66], 'algorithms': [45, 76, 134], '(Williams,': [47], "STOC'14)": [48], '(Abboud,': [50], 'Williams,': [51], 'Yu,': [53], 'SODA': [54], '2015)': [55], 'respectively,': [56], 'ability': [59], 'was': [62], 'open': [63, 112], 'even': [64], 'for': [65, 77, 106], 'algorithms.': [67], 'By': [68], 'reductions,': [69], 'these': [70], 'two': [71], 'results': [72], 'yield': [73], 'faster': [74], 'many': [78], 'other': [79], 'problems.': [80], 'Our': [81], 'techniques': [82], 'can': [83], 'also': [84], 'be': [85], 'used': [86], 'deterministically': [88, 126], 'k-SAT': [90], 'assignments': [91], 'variable': [94], 'formulas': [95], '2n–n/O(k)': [97], 'roughly': [99], 'matching': [100], 'detecting': [107], 'satisfiability': [108], 'resolving': [110], 'an': [111, 122], 'problem': [113], 'Santhanam': [115], '(2013).A': [116], 'key': [117], 'our': [119], 'constructions': [120], 'is': [121], 'efficient': [123], 'way': [124], 'simulate': [127], 'certain': [128], 'probabilistic': [129], 'polynomials': [130], 'critical': [131], 'prior': [136], 'work,': [137], 'carefully': [138], 'applying': [139], 'small-biased': [140], 'sets': [141], 'modulus-amplifying': [143], 'polynomials.': [144]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W4242600797', 'counts_by_year': [{'year': 2024, 'cited_by_count': 4}, {'year': 2023, 'cited_by_count': 3}, {'year': 2022, 'cited_by_count': 4}, {'year': 2021, 'cited_by_count': 3}, {'year': 2020, 'cited_by_count': 3}, {'year': 2019, 'cited_by_count': 8}, {'year': 2018, 'cited_by_count': 2}, {'year': 2017, 'cited_by_count': 4}, {'year': 2016, 'cited_by_count': 2}], 'updated_date': '2024-12-23T08:41:04.824293', 'created_date': '2022-05-12'}