Publication Information

{'id': 'https://openalex.org/W1991584875', 'doi': 'https://doi.org/10.1137/05063605x', 'title': 'Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits', 'display_name': 'Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits', 'publication_year': 2007, 'publication_date': '2007-01-01', 'ids': {'openalex': 'https://openalex.org/W1991584875', 'doi': 'https://doi.org/10.1137/05063605x', 'mag': '1991584875'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1137/05063605x', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S153560523', 'display_name': 'SIAM Journal on Computing', 'issn_l': '0097-5397', 'issn': ['0097-5397', '1095-7111'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310320508', 'host_organization_name': 'Society for Industrial and Applied Mathematics', 'host_organization_lineage': ['https://openalex.org/P4310320508'], 'host_organization_lineage_names': ['Society for Industrial and Applied Mathematics'], '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': False, 'oa_status': 'closed', 'oa_url': None, 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5013053155', 'display_name': 'Zeev Dvir', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I53964585', 'display_name': 'Weizmann Institute of Science', 'ror': 'https://ror.org/0316ej306', 'country_code': 'IL', 'type': 'education', 'lineage': ['https://openalex.org/I53964585']}], 'countries': ['IL'], 'is_corresponding': False, 'raw_author_name': 'Zeev Dvir', 'raw_affiliation_strings': ['Weizmann Institute of Science'], 'affiliations': [{'raw_affiliation_string': 'Weizmann Institute of Science', 'institution_ids': ['https://openalex.org/I53964585']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5004182247', 'display_name': 'Amir Shpilka', 'orcid': 'https://orcid.org/0000-0003-2384-425X'}, 'institutions': [{'id': 'https://openalex.org/I174306211', 'display_name': 'Technion – Israel Institute of Technology', 'ror': 'https://ror.org/03qryx823', 'country_code': 'IL', 'type': 'education', 'lineage': ['https://openalex.org/I174306211']}], 'countries': ['IL'], 'is_corresponding': False, 'raw_author_name': 'Amir Shpilka', 'raw_affiliation_strings': ['TECHNION-Israel Institute of Technology'], 'affiliations': [{'raw_affiliation_string': 'TECHNION-Israel Institute of Technology', 'institution_ids': ['https://openalex.org/I174306211']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 2, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 9.061, 'has_fulltext': True, 'fulltext_origin': 'ngrams', 'cited_by_count': 148, 'citation_normalized_percentile': {'value': 0.999881, 'is_in_top_1_percent': True, 'is_in_top_10_percent': True}, 'cited_by_percentile_year': {'min': 98, 'max': 99}, 'biblio': {'volume': '36', 'issue': '5', 'first_page': '1404', 'last_page': '1434'}, '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.9997, '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/T12072', 'display_name': 'Machine Learning and Algorithms', 'score': 0.9985, '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/zero', 'display_name': 'Zero (linguistics)', 'score': 0.46960744}, {'id': 'https://openalex.org/keywords/constant', 'display_name': 'Constant (computer programming)', 'score': 0.45260468}], 'concepts': [{'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.74109066}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.6242707}, {'id': 'https://openalex.org/C90119067', 'wikidata': 'https://www.wikidata.org/wiki/Q43260', 'display_name': 'Polynomial', 'level': 2, 'score': 0.6240358}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.54418147}, {'id': 'https://openalex.org/C34388435', 'wikidata': 'https://www.wikidata.org/wiki/Q2267362', 'display_name': 'Bounded function', 'level': 2, 'score': 0.53868085}, {'id': 'https://openalex.org/C2778355321', 'wikidata': 'https://www.wikidata.org/wiki/Q17079427', 'display_name': 'Identity (music)', 'level': 2, 'score': 0.47990546}, {'id': 'https://openalex.org/C2780813799', 'wikidata': 'https://www.wikidata.org/wiki/Q3274237', 'display_name': 'Zero (linguistics)', 'level': 2, 'score': 0.46960744}, {'id': 'https://openalex.org/C2777027219', 'wikidata': 'https://www.wikidata.org/wiki/Q1284190', 'display_name': 'Constant (computer programming)', 'level': 2, 'score': 0.45260468}, {'id': 'https://openalex.org/C9376300', 'wikidata': 'https://www.wikidata.org/wiki/Q168817', 'display_name': 'Algebraic number', 'level': 2, 'score': 0.4142531}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.09987241}, {'id': 'https://openalex.org/C41895202', 'wikidata': 'https://www.wikidata.org/wiki/Q8162', 'display_name': 'Linguistics', '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/C24890656', 'wikidata': 'https://www.wikidata.org/wiki/Q82811', 'display_name': 'Acoustics', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.0}, {'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/C121332964', 'wikidata': 'https://www.wikidata.org/wiki/Q413', 'display_name': 'Physics', 'level': 0, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1137/05063605x', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S153560523', 'display_name': 'SIAM Journal on Computing', 'issn_l': '0097-5397', 'issn': ['0097-5397', '1095-7111'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310320508', 'host_organization_name': 'Society for Industrial and Applied Mathematics', 'host_organization_lineage': ['https://openalex.org/P4310320508'], 'host_organization_lineage_names': ['Society for Industrial and Applied Mathematics'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}], 'best_oa_location': None, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 39, 'referenced_works': ['https://openalex.org/W1505096007', 'https://openalex.org/W1555149635', 'https://openalex.org/W1590864168', 'https://openalex.org/W1594962164', 'https://openalex.org/W1599026900', 'https://openalex.org/W1896605895', 'https://openalex.org/W1967361897', 'https://openalex.org/W1970056983', 'https://openalex.org/W1973342538', 'https://openalex.org/W1974331311', 'https://openalex.org/W1981234161', 'https://openalex.org/W2000211775', 'https://openalex.org/W2026036943', 'https://openalex.org/W2027528470', 'https://openalex.org/W2033773511', 'https://openalex.org/W2043667326', 'https://openalex.org/W2053086236', 'https://openalex.org/W2055425281', 'https://openalex.org/W2062965695', 'https://openalex.org/W2070279173', 'https://openalex.org/W2070432726', 'https://openalex.org/W2070661348', 'https://openalex.org/W2073346043', 'https://openalex.org/W2079560560', 'https://openalex.org/W2080132708', 'https://openalex.org/W2080529336', 'https://openalex.org/W2082846050', 'https://openalex.org/W2087207261', 'https://openalex.org/W2094878497', 'https://openalex.org/W2103961582', 'https://openalex.org/W2113291984', 'https://openalex.org/W2120217745', 'https://openalex.org/W2121894367', 'https://openalex.org/W2150884088', 'https://openalex.org/W2157915592', 'https://openalex.org/W2159341052', 'https://openalex.org/W2171403864', 'https://openalex.org/W2177482211', 'https://openalex.org/W2611398525'], 'related_works': ['https://openalex.org/W4386900933', 'https://openalex.org/W4385301946', 'https://openalex.org/W4297797135', 'https://openalex.org/W3125672081', 'https://openalex.org/W3013085049', 'https://openalex.org/W2165296851', 'https://openalex.org/W2053206769', 'https://openalex.org/W2044942888', 'https://openalex.org/W1673581201', 'https://openalex.org/W1560496689'], 'abstract_inverted_index': {'In': [0, 84, 255, 430], 'this': [1, 112], 'work': [2], 'we': [3, 45, 55, 86, 216, 257], 'study': [4], 'two,': [5], 'seemingly': [6], 'unrelated,': [7], 'notions.': [8, 83], 'Locally': [9], 'decodable': [10], 'codes': [11, 14], '(LDCs)': [12], 'are': [13, 46], 'that': [15, 94, 135, 152, 165, 225, 250, 259, 308, 318], 'allow': [16], 'the': [17, 30, 39, 60, 81, 88, 154, 173, 187, 193, 196, 205, 208, 252, 279, 334, 364, 390, 414, 433], 'recovery': [18], 'of': [19, 27, 29, 38, 42, 118, 172, 195, 207, 228, 233, 268, 281, 329, 389, 397, 413, 421, 436], 'each': [20], 'message': [21], 'bit': [22], 'from': [23, 136], 'a': [24, 48, 51, 78, 101, 147, 219, 239, 246, 262, 300, 305, 315, 326], 'constant': [25], 'number': [26, 280, 328], 'entries': [28], 'codeword.': [31], 'Polynomial': [32], 'identity': [33, 74], 'testing': [34, 75], '(PIT)': [35], 'is': [36, 62, 100, 168, 264, 275, 336], 'one': [37, 157], 'fundamental': [40], 'problems': [41], 'algebraic': [43], 'complexity:': [44], 'given': [47], 'circuit': [49, 141, 263, 335], 'computing': [50], 'multivariate': [52], 'polynomial': [53, 61, 73, 197, 269, 321, 343], 'and': [54, 71, 76, 179, 202, 267, 313, 323, 372, 385, 409, 453], 'have': [56, 287], 'to': [57, 177], 'determine': [58], 'whether': [59], 'identically': [63], 'zero.': [64], 'We': [65, 92, 133, 237, 291], 'improve': [66], 'known': [67, 114, 357], 'results': [68], 'on': [69, 72, 395, 419], 'LDCs': [70], 'show': [77, 93, 134, 258], 'relation': [79], 'between': [80], 'two': [82, 105, 223], 'particular': [85, 256], 'obtain': [87], 'following': [89], 'results:': [90], '(1)': [91], 'if': [95, 260], '$E:': [96], '\\mathbb{F}^n': [97], '\\mapsto': [98], '\\mathbb{F}^m$': [99], 'linear': [102, 182, 209, 220], 'LDC': [103, 221], 'with': [104, 146, 222, 245, 299, 440], 'queries,': [106], 'then': [107, 271], '$m': [108], '=': [109], '\\exp(\\Omega(n))$.': [110], 'Previously': [111, 345], 'was': [113], 'only': [115, 276, 325, 358], 'for': [116, 242, 296, 350, 359, 432], 'fields': [117], 'size': [119], '$\\ll': [120], '2^n$': [121], '[O.': [122], 'Goldreich': [123], 'et': [124], 'al.,': [125], 'Comput.': [126], 'Complexity,': [127], '15': [128], '(2006),': [129], 'pp.': [130, 381, 404, 428], '263–296].': [131], '(2)': [132], 'every': [137], 'depth': [138, 354, 360, 437], '3': [139, 438], 'arithmetic': [140], '($\\Sigma\\Pi\\Sigma$': [142], 'circuit),': [143], '${\\cal': [144, 166, 200, 213], 'C}$,': [145], 'bounded': [148, 247, 301, 353], '(constant)': [149], 'top': [150, 248, 302], 'fan‐in': [151], 'computes': [153], 'zero': [155, 253], 'polynomial,': [156], 'can': [158, 217], 'construct': [159, 218], 'an': [160, 447], 'LDC.': [161], 'More': [162], 'formally,': [163], 'assume': [164], 'C}$': [167, 201], 'minimal': [169], '(no': [170, 181], 'subset': [171], 'multiplication': [174, 188, 442], 'gates': [175, 443], 'sums': [176], 'zero)': [178], 'simple': [180], 'function': [183], 'appears': [184], 'in': [185, 212, 278, 310, 320, 342, 352], 'all': [186], 'gates).': [189], 'Denote': [190], 'by': [191, 199, 203, 231, 451], 'd': [192], 'degree': [194], 'computed': [198], 'r': [204], 'rank': [206], 'functions': [210], 'appearing': [211], 'C}$.': [214], 'Then': [215], 'queries': [224], 'encodes': [226], 'messages': [227], 'length': [229, 234], '$r/{\\operatorname{polylog}(d)}$': [230], 'codewords': [232], '$O(d)$.': [235], '(3)': [236], 'prove': [238], 'structural': [240], 'theorem': [241], '$\\Sigma\\Pi\\Sigma$': [243, 297], 'circuits,': [244], 'fan‐in,': [249], 'compute': [251], 'polynomial.': [254], 'such': [261], 'simple,': [265], 'minimal,': [266], 'size,': [270], 'its': [272], 'rank,': [273], 'r,': [274], 'polylogarithmic': [277, 327], 'variables': [282], '(a': [283], 'priori': [284], 'it': [285], 'could': [286], 'been': [288], 'linear).': [289], '(4)': [290], 'give': [292], 'new': [293], 'PIT': [294, 351], 'algorithms': [295, 349], 'circuits': [298, 355, 362, 439], 'fan‐in:': [303], '(a)': [304], 'deterministic': [306, 339, 346], 'algorithm': [307, 317, 340], 'runs': [309, 319, 341], 'quasipolynomial': [311], 'time,': [312], '(b)': [314], 'randomized': [316], 'time': [322, 348], 'uses': [324], 'random': [330], 'bits.': [331], 'Moreover,': [332], 'when': [333], 'multilinear,': [337], 'our': [338, 444], 'time.': [344], 'subexponential': [347], 'were': [356], '2': [361], '(in': [363], 'black': [365], 'box': [366], 'model)': [367], '[D.': [368], 'Grigoriev,': [369], 'M.': [370, 373, 383], 'Karpinski,': [371], 'F.': [374], 'Singer,': [375], 'SIAM': [376], 'J.': [377], 'Comput.,': [378], '19': [379], '(1990),': [380], '1059–1063;': [382], 'Ben‐Or': [384], 'P.': [386], 'Tiwari,': [387], 'Proceedings': [388, 412], '20th': [391], 'Annual': [392, 416], 'ACM': [393, 399, 417, 423], 'Symposium': [394, 418], 'Theory': [396, 420], 'Computing,': [398, 422], 'Press,': [400, 424], 'New': [401, 425], 'York,': [402, 426], '1988,': [403], '301–309;': [405], 'A.': [406], 'R.': [407], 'Klivans': [408, 452], 'D.': [410], 'Spielman,': [411], '33rd': [415], '2001,': [427], '216–223].': [429], 'particular,': [431], 'special': [434], 'case': [435], 'three': [441], 'result': [445], 'resolves': [446], 'open': [448], 'question': [449], 'asked': [450], 'Spielman.': [454]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W1991584875', 'counts_by_year': [{'year': 2024, 'cited_by_count': 4}, {'year': 2023, 'cited_by_count': 2}, {'year': 2022, 'cited_by_count': 7}, {'year': 2021, 'cited_by_count': 7}, {'year': 2020, 'cited_by_count': 2}, {'year': 2019, 'cited_by_count': 7}, {'year': 2018, 'cited_by_count': 7}, {'year': 2017, 'cited_by_count': 6}, {'year': 2016, 'cited_by_count': 13}, {'year': 2015, 'cited_by_count': 15}, {'year': 2014, 'cited_by_count': 15}, {'year': 2013, 'cited_by_count': 10}, {'year': 2012, 'cited_by_count': 9}], 'updated_date': '2024-12-07T22:00:29.515547', 'created_date': '2016-06-24'}