Publication Information

{'id': 'https://openalex.org/W2980711752', 'doi': 'https://doi.org/10.1145/3322811', 'title': 'Distributed Detection of Cycles', 'display_name': 'Distributed Detection of Cycles', 'publication_year': 2019, 'publication_date': '2019-09-30', 'ids': {'openalex': 'https://openalex.org/W2980711752', 'doi': 'https://doi.org/10.1145/3322811', 'mag': '2980711752'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/3322811', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S2483380313', 'display_name': 'ACM Transactions on Parallel Computing', 'issn_l': '2329-4949', 'issn': ['2329-4949', '2329-4957'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319798', 'host_organization_name': 'Association for Computing Machinery', 'host_organization_lineage': ['https://openalex.org/P4310319798'], 'host_organization_lineage_names': ['Association for Computing Machinery'], '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': 'https://research.aalto.fi/files/61088586/ddoc.pdf', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5110465085', 'display_name': 'Pierre Fraigniaud', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I4210117673', 'display_name': 'Institut de Recherche en Informatique Fondamentale', 'ror': 'https://ror.org/02krdtz55', 'country_code': 'FR', 'type': 'facility', 'lineage': ['https://openalex.org/I1294671590', 'https://openalex.org/I204730241', 'https://openalex.org/I4210089394', 'https://openalex.org/I4210117673', 'https://openalex.org/I4210139971']}, {'id': 'https://openalex.org/I4210099593', 'display_name': 'Computer Algorithms for Medicine', 'ror': 'https://ror.org/00zky6d38', 'country_code': 'AT', 'type': 'facility', 'lineage': ['https://openalex.org/I4210099593']}, {'id': 'https://openalex.org/I169173203', 'display_name': 'Délégation Paris 7', 'ror': 'https://ror.org/00bw5n526', 'country_code': 'FR', 'type': 'government', 'lineage': ['https://openalex.org/I154526488', 'https://openalex.org/I169173203']}, {'id': 'https://openalex.org/I204730241', 'display_name': 'Université Paris Cité', 'ror': 'https://ror.org/05f82e368', 'country_code': 'FR', 'type': 'education', 'lineage': ['https://openalex.org/I204730241']}, {'id': 'https://openalex.org/I1294671590', 'display_name': 'Centre National de la Recherche Scientifique', 'ror': 'https://ror.org/02feahw73', 'country_code': 'FR', 'type': 'government', 'lineage': ['https://openalex.org/I1294671590']}], 'countries': ['AT', 'FR'], 'is_corresponding': False, 'raw_author_name': 'Pierre Fraigniaud', 'raw_affiliation_strings': ['CNRS and University Paris Diderot, Paris, France', 'Institut de Recherche en Informatique Fondamentale', 'Networks, Graphs and Algorithms'], 'affiliations': [{'raw_affiliation_string': 'Institut de Recherche en Informatique Fondamentale', 'institution_ids': ['https://openalex.org/I4210117673']}, {'raw_affiliation_string': 'Networks, Graphs and Algorithms', 'institution_ids': ['https://openalex.org/I4210099593']}, {'raw_affiliation_string': 'CNRS and University Paris Diderot, Paris, France', 'institution_ids': ['https://openalex.org/I169173203', 'https://openalex.org/I204730241', 'https://openalex.org/I1294671590']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5042405670', 'display_name': 'Dennis Olivetti', 'orcid': 'https://orcid.org/0000-0002-6600-6443'}, 'institutions': [{'id': 'https://openalex.org/I4210117673', 'display_name': 'Institut de Recherche en Informatique Fondamentale', 'ror': 'https://ror.org/02krdtz55', 'country_code': 'FR', 'type': 'facility', 'lineage': ['https://openalex.org/I1294671590', 'https://openalex.org/I204730241', 'https://openalex.org/I4210089394', 'https://openalex.org/I4210117673', 'https://openalex.org/I4210139971']}, {'id': 'https://openalex.org/I9927081', 'display_name': 'Aalto University', 'ror': 'https://ror.org/020hwjq30', 'country_code': 'FI', 'type': 'education', 'lineage': ['https://openalex.org/I9927081']}], 'countries': ['FI', 'FR'], 'is_corresponding': False, 'raw_author_name': 'Dennis Olivetti', 'raw_affiliation_strings': ['Aalto University, Konemiehentie, Espoo, Finland', 'Institut de Recherche en Informatique Fondamentale'], 'affiliations': [{'raw_affiliation_string': 'Institut de Recherche en Informatique Fondamentale', 'institution_ids': ['https://openalex.org/I4210117673']}, {'raw_affiliation_string': 'Aalto University, Konemiehentie, Espoo, Finland', 'institution_ids': ['https://openalex.org/I9927081']}]}], 'institution_assertions': [], 'countries_distinct_count': 3, 'institutions_distinct_count': 6, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 0.826, 'has_fulltext': False, 'cited_by_count': 12, 'citation_normalized_percentile': {'value': 0.866286, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 87, 'max': 88}, 'biblio': {'volume': '6', 'issue': '3', 'first_page': '1', 'last_page': '20'}, '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/T10237', 'display_name': 'Cryptography and Data Security', 'score': 0.9995, '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'}}, {'id': 'https://openalex.org/T12288', 'display_name': 'Optimization and Search Problems', 'score': 0.9992, 'subfield': {'id': 'https://openalex.org/subfields/1705', 'display_name': 'Computer Networks and Communications'}, '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/constant', 'display_name': 'Constant (computer programming)', 'score': 0.80380154}, {'id': 'https://openalex.org/keywords/property-testing', 'display_name': 'Property testing', 'score': 0.7300065}], 'concepts': [{'id': 'https://openalex.org/C2777027219', 'wikidata': 'https://www.wikidata.org/wiki/Q1284190', 'display_name': 'Constant (computer programming)', 'level': 2, 'score': 0.80380154}, {'id': 'https://openalex.org/C189950617', 'wikidata': 'https://www.wikidata.org/wiki/Q937228', 'display_name': 'Property (philosophy)', 'level': 2, 'score': 0.74929845}, {'id': 'https://openalex.org/C123842658', 'wikidata': 'https://www.wikidata.org/wiki/Q2918980', 'display_name': 'Property testing', 'level': 2, 'score': 0.7300065}, {'id': 'https://openalex.org/C130120984', 'wikidata': 'https://www.wikidata.org/wiki/Q2835898', 'display_name': 'Distributed algorithm', 'level': 2, 'score': 0.6812011}, {'id': 'https://openalex.org/C2779343474', 'wikidata': 'https://www.wikidata.org/wiki/Q3109175', 'display_name': 'Context (archaeology)', 'level': 2, 'score': 0.678417}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.6756005}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.4506663}, {'id': 'https://openalex.org/C80444323', 'wikidata': 'https://www.wikidata.org/wiki/Q2878974', 'display_name': 'Theoretical computer science', 'level': 1, 'score': 0.39152363}, {'id': 'https://openalex.org/C120314980', 'wikidata': 'https://www.wikidata.org/wiki/Q180634', 'display_name': 'Distributed computing', 'level': 1, 'score': 0.35836446}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.32832813}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.2572622}, {'id': 'https://openalex.org/C151730666', 'wikidata': 'https://www.wikidata.org/wiki/Q7205', 'display_name': 'Paleontology', '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/C111472728', 'wikidata': 'https://www.wikidata.org/wiki/Q9471', 'display_name': 'Epistemology', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C86803240', 'wikidata': 'https://www.wikidata.org/wiki/Q420', 'display_name': 'Biology', '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': 5, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/3322811', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S2483380313', 'display_name': 'ACM Transactions on Parallel Computing', 'issn_l': '2329-4949', 'issn': ['2329-4949', '2329-4957'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319798', 'host_organization_name': 'Association for Computing Machinery', 'host_organization_lineage': ['https://openalex.org/P4310319798'], 'host_organization_lineage_names': ['Association for Computing Machinery'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://hal.inria.fr/hal-02433486', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306402512', 'display_name': 'HAL (Le Centre pour la Communication Scientifique Directe)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I1294671590', 'host_organization_name': 'Centre National de la Recherche Scientifique', 'host_organization_lineage': ['https://openalex.org/I1294671590'], 'host_organization_lineage_names': ['Centre National de la Recherche Scientifique'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://hal.inria.fr/hal-03100189', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306402512', 'display_name': 'HAL (Le Centre pour la Communication Scientifique Directe)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I1294671590', 'host_organization_name': 'Centre National de la Recherche Scientifique', 'host_organization_lineage': ['https://openalex.org/I1294671590'], 'host_organization_lineage_names': ['Centre National de la Recherche Scientifique'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'https://aaltodoc.aalto.fi/handle/123456789/103145', 'pdf_url': 'https://research.aalto.fi/files/61088586/ddoc.pdf', 'source': {'id': 'https://openalex.org/S4306401663', 'display_name': 'Aaltodoc (Aalto University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I9927081', 'host_organization_name': 'Aalto University', 'host_organization_lineage': ['https://openalex.org/I9927081'], 'host_organization_lineage_names': ['Aalto University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'acceptedVersion', 'is_accepted': True, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/1706.03992', 'pdf_url': 'https://arxiv.org/pdf/1706.03992', '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': 'https://aaltodoc.aalto.fi/handle/123456789/103145', 'pdf_url': 'https://research.aalto.fi/files/61088586/ddoc.pdf', 'source': {'id': 'https://openalex.org/S4306401663', 'display_name': 'Aaltodoc (Aalto University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I9927081', 'host_organization_name': 'Aalto University', 'host_organization_lineage': ['https://openalex.org/I9927081'], 'host_organization_lineage_names': ['Aalto University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'acceptedVersion', 'is_accepted': True, 'is_published': False}, 'sustainable_development_goals': [{'score': 0.82, 'id': 'https://metadata.un.org/sdg/16', 'display_name': 'Peace, justice, and strong institutions'}], 'grants': [{'funder': 'https://openalex.org/F4320321108', 'funder_display_name': 'Academy of Finland', 'award_id': '285721'}, {'funder': 'https://openalex.org/F4320325505', 'funder_display_name': 'Agence Nationale pour le Développement de la Recherche Universitaire', 'award_id': 'DESCARTES'}], 'datasets': [], 'versions': [], 'referenced_works_count': 35, 'referenced_works': ['https://openalex.org/W132161852', 'https://openalex.org/W1568961751', 'https://openalex.org/W1586904125', 'https://openalex.org/W1600101873', 'https://openalex.org/W1648776928', 'https://openalex.org/W1965645254', 'https://openalex.org/W1975579567', 'https://openalex.org/W1980816908', 'https://openalex.org/W1981234161', 'https://openalex.org/W1990490082', 'https://openalex.org/W1999120866', 'https://openalex.org/W2017345786', 'https://openalex.org/W2025809519', 'https://openalex.org/W2030160771', 'https://openalex.org/W2056295140', 'https://openalex.org/W2073448902', 'https://openalex.org/W2093276208', 'https://openalex.org/W2139374679', 'https://openalex.org/W2144475416', 'https://openalex.org/W2166366653', 'https://openalex.org/W2184633425', 'https://openalex.org/W2253610808', 'https://openalex.org/W2289937698', 'https://openalex.org/W2366922697', 'https://openalex.org/W2495638761', 'https://openalex.org/W2570310514', 'https://openalex.org/W2605289172', 'https://openalex.org/W2773213286', 'https://openalex.org/W2962803529', 'https://openalex.org/W2963005178', 'https://openalex.org/W3008660429', 'https://openalex.org/W4205300528', 'https://openalex.org/W4255563008', 'https://openalex.org/W4300486881', 'https://openalex.org/W621782861'], 'related_works': ['https://openalex.org/W4298661057', 'https://openalex.org/W2980711752', 'https://openalex.org/W2963363569', 'https://openalex.org/W2949229117', 'https://openalex.org/W267063485', 'https://openalex.org/W2160856947', 'https://openalex.org/W2108852611', 'https://openalex.org/W2073966617', 'https://openalex.org/W1972927969', 'https://openalex.org/W1566995037'], 'abstract_inverted_index': {'Distributed': [0], 'property': [1, 131], 'testing': [2, 132], 'in': [3, 24, 40, 53, 77, 88, 139, 149], 'networks': [4], 'has': [5], 'been': [6], 'introduced': [7], 'by': [8, 59, 117], 'Brakerski': [9], 'and': [10, 37, 181], 'Patt-Shamir': [11], '[6],': [12], 'with': [13, 102], 'the': [14, 18, 86, 112, 119, 150, 173, 177], 'objective': [15], 'of': [16, 20, 57, 81, 114, 143], 'detecting': [17], 'presence': [19], 'large': [21], 'dense': [22], 'sub-networks': [23], 'a': [25, 41, 54, 60, 64, 78, 129, 140], 'distributed': [26, 61, 130, 155], 'manner.': [27], 'Recently,': [28], 'Censor-Hillel': [29], 'et': [30, 68], 'al.': [31, 69], '[7]': [32], 'have': [33, 47, 71], 'revisited': [34], 'this': [35, 107], 'notion': [36], 'formalized': [38], 'it': [39], 'broader': [42], 'context.': [43], 'In': [44, 63, 106], 'particular,': [45], 'they': [46], 'shown': [48, 72, 93], 'how': [49, 73], 'to': [50, 74, 95, 97], 'detect': [51, 75], '3-cycles': [52], 'constant': [55, 79, 141], 'number': [56, 80, 142], 'rounds': [58, 82], 'algorithm.': [62], 'follow-up': [65], 'work,': [66], 'Fraigniaud': [67], '[21]': [70], '4-cycles': [76], 'as': [83], 'well.': [84], 'However,': [85], 'techniques': [87], 'these': [89, 146], 'latter': [90], 'works': [91], 'were': [92], 'not': [94], 'generalize': [96], 'larger': [98], 'cycles': [99], 'C': [100, 135], 'k': [101, 103, 124, 136], '≥': [104, 125], '5.': [105], 'article,': [108], 'we': [109], 'completely': [110], 'settle': [111], 'problem': [113], 'cycle': [115], 'detection': [116], 'establishing': [118], 'following': [120], 'result:': [121], 'For': [122], 'every': [123], '3,': [126], 'there': [127], 'exists': [128], 'algorithm': [133, 159], 'for': [134, 154], '-freeness,': [137], 'performing': [138], 'rounds.': [144], 'All': [145], 'results': [147], 'hold': [148], 'classical': [151], 'congest': [152], 'model': [153], 'network': [156], 'computing.': [157], 'Our': [158], 'is': [160, 165, 172], '1-sided': [161], 'error.': [162], 'Its': [163], 'round-complexity': [164], 'O': [166], '(1ϵ)': [167], 'where': [168], 'ϵ': [169], '∈': [170], '(0,1)': [171], 'property-testing': [174], 'parameter': [175], 'measuring': [176], 'gap': [178], 'between': [179], 'legal': [180], 'illegal': [182], 'instances.': [183]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2980711752', 'counts_by_year': [{'year': 2024, 'cited_by_count': 5}, {'year': 2023, 'cited_by_count': 2}, {'year': 2022, 'cited_by_count': 1}, {'year': 2021, 'cited_by_count': 1}, {'year': 2020, 'cited_by_count': 3}], 'updated_date': '2025-01-05T20:22:28.519850', 'created_date': '2019-10-25'}