Publication Information

{'id': 'https://openalex.org/W2049918060', 'doi': 'https://doi.org/10.1109/focs.2006.13', 'title': 'Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification', 'display_name': 'Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification', 'publication_year': 2006, 'publication_date': '2006-10-01', 'ids': {'openalex': 'https://openalex.org/W2049918060', 'doi': 'https://doi.org/10.1109/focs.2006.13', 'mag': '2049918060'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1109/focs.2006.13', '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': False, 'oa_status': 'closed', 'oa_url': None, 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5002208831', 'display_name': 'Russell Impagliazzo', 'orcid': 'https://orcid.org/0000-0003-3236-9796'}, 'institutions': [{'id': 'https://openalex.org/I36258959', 'display_name': 'University of California, San Diego', 'ror': 'https://ror.org/0168r3w48', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I36258959']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Russell Impagliazzo', 'raw_affiliation_strings': ['University of California. San Diego, USA'], 'affiliations': [{'raw_affiliation_string': 'University of California. San Diego, USA', 'institution_ids': ['https://openalex.org/I36258959']}]}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5075959430', 'display_name': 'Ragesh Jaiswal', 'orcid': 'https://orcid.org/0009-0002-4475-0922'}, 'institutions': [{'id': 'https://openalex.org/I36258959', 'display_name': 'University of California, San Diego', 'ror': 'https://ror.org/0168r3w48', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I36258959']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Ragesh Jaiswal', 'raw_affiliation_strings': ['University of California. San Diego, USA'], 'affiliations': [{'raw_affiliation_string': 'University of California. San Diego, USA', 'institution_ids': ['https://openalex.org/I36258959']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5066747130', 'display_name': 'Valentine Kabanets', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I18014758', 'display_name': 'Simon Fraser University', 'ror': 'https://ror.org/0213rcc28', 'country_code': 'CA', 'type': 'education', 'lineage': ['https://openalex.org/I18014758']}], 'countries': ['CA'], 'is_corresponding': False, 'raw_author_name': 'Valentine Kabanets', 'raw_affiliation_strings': ['Simon Fraser University CANADA'], 'affiliations': [{'raw_affiliation_string': 'Simon Fraser University CANADA', 'institution_ids': ['https://openalex.org/I18014758']}]}], 'institution_assertions': [], 'countries_distinct_count': 2, 'institutions_distinct_count': 2, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 4.379, 'has_fulltext': True, 'fulltext_origin': 'ngrams', 'cited_by_count': 38, 'citation_normalized_percentile': {'value': 0.860759, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 91, 'max': 92}, 'biblio': {'volume': None, 'issue': None, 'first_page': '187', 'last_page': '196'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10237', 'display_name': 'Cryptography and Data Security', 'score': 0.9987, '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'}}, 'topics': [{'id': 'https://openalex.org/T10237', 'display_name': 'Cryptography and Data Security', 'score': 0.9987, '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/T11130', 'display_name': 'Coding theory and cryptography', 'score': 0.9984, '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/T10796', 'display_name': 'Cooperative Communication and Network Coding', 'score': 0.9982, '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': [], 'concepts': [{'id': 'https://openalex.org/C57273362', 'wikidata': 'https://www.wikidata.org/wiki/Q576722', 'display_name': 'Decoding methods', 'level': 2, 'score': 0.46170977}, {'id': 'https://openalex.org/C90673727', 'wikidata': 'https://www.wikidata.org/wiki/Q901718', 'display_name': 'Product (mathematics)', 'level': 2, 'score': 0.4553145}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.38803405}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.34930968}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.3348925}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.28413743}, {'id': 'https://openalex.org/C2524010', 'wikidata': 'https://www.wikidata.org/wiki/Q8087', 'display_name': 'Geometry', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1109/focs.2006.13', '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': [{'score': 0.4, 'id': 'https://metadata.un.org/sdg/8', 'display_name': 'Decent work and economic growth'}], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 40, 'referenced_works': ['https://openalex.org/W1505096007', 'https://openalex.org/W1563159456', 'https://openalex.org/W1572772224', 'https://openalex.org/W1583202823', 'https://openalex.org/W1901622511', 'https://openalex.org/W1967175855', 'https://openalex.org/W1970259241', 'https://openalex.org/W1980327536', 'https://openalex.org/W1994091697', 'https://openalex.org/W1998918799', 'https://openalex.org/W2014860393', 'https://openalex.org/W2019578639', 'https://openalex.org/W2021736779', 'https://openalex.org/W2027528470', 'https://openalex.org/W2042587503', 'https://openalex.org/W2045377861', 'https://openalex.org/W2062855793', 'https://openalex.org/W2068096733', 'https://openalex.org/W2099111195', 'https://openalex.org/W2100661986', 'https://openalex.org/W2103012681', 'https://openalex.org/W2107324709', 'https://openalex.org/W2122270497', 'https://openalex.org/W2124619161', 'https://openalex.org/W2135134090', 'https://openalex.org/W2135456059', 'https://openalex.org/W2138036903', 'https://openalex.org/W2143112402', 'https://openalex.org/W2148352980', 'https://openalex.org/W2160403361', 'https://openalex.org/W2168991396', 'https://openalex.org/W2169453948', 'https://openalex.org/W2173249896', 'https://openalex.org/W2294870549', 'https://openalex.org/W2611398525', 'https://openalex.org/W2998808137', 'https://openalex.org/W3144881883', 'https://openalex.org/W3150645827', 'https://openalex.org/W4212956348', 'https://openalex.org/W4213042755'], 'related_works': ['https://openalex.org/W4396701345', 'https://openalex.org/W4396696052', 'https://openalex.org/W4391375266', 'https://openalex.org/W2748952813', 'https://openalex.org/W2390279801', 'https://openalex.org/W2376932109', 'https://openalex.org/W2358668433', 'https://openalex.org/W2073681303', 'https://openalex.org/W2051487156', 'https://openalex.org/W2001405890'], 'abstract_inverted_index': {'We': [0, 130], 'consider': [1], 'the': [2, 15, 34, 64, 81, 98, 107, 112, 152, 222, 226, 272, 286, 328], 'problem': [3], 'of': [4, 20, 80, 100, 103, 140, 157, 167, 174, 185, 195, 207, 225, 302, 330, 338, 372, 405], 'approximately': [5, 293], 'locally': [6, 282], 'list-decoding': [7, 139, 254], 'direct': [8, 17, 108, 141, 154, 274], 'product': [9, 18, 109, 142, 155, 275], 'codes.': [10, 143], 'For': [11], 'a': [12, 147, 172, 243, 251, 345], 'parameter': [13], 'k,': [14], 'k-wise': [16, 153, 273], 'encoding': [19, 156], 'an': [21, 26, 132, 164, 311], 'N-bit': [22, 179], 'message': [23, 159], 'msg': [24, 160, 199], 'is': [25, 83, 228, 344, 376], 'N': [27, 123, 232], '<sup': [28, 38, 59, 213, 239, 265, 321, 349, 368, 381, 401], 'xmlns:mml="http://www.w3.org/1998/Math/MathML"': [29, 39, 46, 53, 60, 70, 77, 86, 90, 214, 240, 266, 322, 325, 350, 353, 369, 382, 385, 402], 'xmlns:xlink="http://www.w3.org/1999/xlink">k</sup>': [30, 40, 61], '-length': [31], 'string': [32], 'over': [33, 285], 'alphabet': [35], '{0,': [36], 'l}': [37], 'indexed': [41], 'by': [42, 359, 391], 'k-tuples': [43], '(i': [44, 68], '<sub': [45, 52, 69, 76, 85, 89, 324, 352, 384], 'xmlns:xlink="http://www.w3.org/1999/xlink">1</sub>': [47, 71, 87], ',': [48, 72, 327], '..': [49, 73], '.,': [50, 74], 'i': [51, 75], 'xmlns:xlink="http://www.w3.org/1999/xlink">k</sub>': [54, 78, 91], ')': [55, 79], 'isin': [56], '{1,...,': [57], 'N}': [58], 'so': [62], 'that': [63, 191, 218, 256, 355, 365, 387], 'symbol': [65], 'at': [66, 162, 192, 201], 'position': [67], 'codeword': [82], 'msg(i': [84], ')...msg(i': [88], ').': [92], 'Such': [93], 'codes': [94, 276, 284], 'arise': [95], 'naturally': [96], 'in': [97, 161, 200, 230, 258, 261, 347, 379], 'context': [99], 'hardness': [101, 317], 'amplification': [102, 318], 'Boolean': [104, 176, 188], 'functions': [105], 'via': [106], 'lemma': [110], '(and': [111], 'closely': [113], 'related': [114], 'Yao': [115], "'s": [116], 'XOR': [117], 'Lemma),': [118], 'where': [119], 'typically': [120], 'k': [121, 125], 'Lt': [122], '(e.g.,': [124], '=': [126, 211, 220, 308], 'poly': [127], 'log': [128, 186, 231, 268], 'N).': [129], 'describe': [131], 'efficient': [133], 'randomized': [134, 252], 'algorithm': [135, 170, 227, 255, 362, 394], 'for': [136, 209, 242, 319], 'approximate': [137, 253], 'local': [138], 'Given': [144], 'access': [145], 'to': [146, 333], 'word': [148], 'which': [149, 289], 'agrees': [150, 197], 'with': [151, 198, 277], 'some': [158], 'least': [163, 193, 202], 'epsiv': [165, 219, 236, 238, 300, 307], 'fraction': [166, 206, 301, 371, 404], 'positions,': [168, 208], 'our': [169], 'outputs': [171], 'list': [173], 'poly(l/epsiv)': [175], 'circuits': [177], 'computing': [178], 'strings': [180], '(viewed': [181], 'as': [182, 304, 306], 'truth': [183], 'tables': [184], 'N-variable': [187], 'functions)': [189], 'such': [190], 'one': [194, 336], 'them': [196], '1': [203, 366], '-': [204, 299], 'delta': [205, 210], 'O(k': [212], 'xmlns:xlink="http://www.w3.org/1999/xlink">-0.1</sup>': [215], '),': [216], 'provided': [217], 'Omega(poly(l/k);': [221], 'running': [223], 'time': [224, 259], 'polynomial': [229], 'and': [233], '1/epsiv.': [234], 'When': [235], '>': [237, 247], 'xmlns:xlink="http://www.w3.org/1999/xlink">kalpha</sup>': [241], 'certain': [244], 'constant': [245], 'alpha': [246], '0,': [248], 'we': [249, 280, 314], 'get': [250, 315], 'runs': [257], 'quasi-polynomial': [260], '1/epsiv': [262], '(i.e.,': [263], '(1/epsiv)': [264], 'xmlns:xlink="http://www.w3.org/1999/xlink">poly': [267], '1</sup>': [269], 'epsiv/)By': [270], 'concatenating': [271], 'Hadamard': [278], 'codes,': [279], 'obtain': [281], 'list-decodable': [283], 'binary': [287], 'alphabet,': [288], 'can': [290], 'be': [291, 357, 389], 'efficiently': [292], 'list-decoded': [294], 'from': [295], 'fewer': [296], 'than': [297, 397], 'frac12': [298, 398], 'corruptions': [303], 'long': [305], 'Omega(poly(l/k)).': [309], 'As': [310], 'immediate': [312], 'application,': [313], 'uniform': [316], 'P': [320, 348, 380], 'xmlns:xlink="http://www.w3.org/1999/xlink">NP</sup>': [323, 351, 383], 'xmlns:xlink="http://www.w3.org/1999/xlink">par</sub>': [326, 354, 386], 'class': [329], 'languages': [331], 'reducible': [332], 'NP': [334], 'through': [335], 'round': [337], 'parallel': [339], 'oracle': [340], 'queries:': [341], 'If': [342], 'there': [343, 375], 'language': [346, 378], 'cannot': [356, 388], 'decided': [358, 390], 'any': [360, 392], 'BPP': [361, 393], 'on': [363, 395], 'more': [364, 396], '$1/n': [367], 'xmlns:xlink="http://www.w3.org/1999/xlink">Omega(1)</sup>': [370], 'inputs,': [373], 'then': [374], 'another': [377], '+': [399], '1/n': [400], 'xmlns:xlink="http://www.w3.org/1999/xlink">omega(1)</sup>': [403], 'inputs': [406]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2049918060', 'counts_by_year': [{'year': 2020, 'cited_by_count': 1}, {'year': 2019, 'cited_by_count': 1}, {'year': 2017, 'cited_by_count': 1}, {'year': 2014, 'cited_by_count': 1}, {'year': 2013, 'cited_by_count': 1}, {'year': 2012, 'cited_by_count': 1}], 'updated_date': '2024-12-10T13:28:07.496892', 'created_date': '2016-06-24'}