Publication Information

{'id': 'https://openalex.org/W3095276197', 'doi': 'https://doi.org/10.1137/20n975154', 'title': 'Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018)', 'display_name': 'Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018)', 'publication_year': 2020, 'publication_date': '2020-01-01', 'ids': {'openalex': 'https://openalex.org/W3095276197', 'doi': 'https://doi.org/10.1137/20n975154', 'mag': '3095276197'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1137/20n975154', '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/A5019616211', 'display_name': 'Thomas Vidick', 'orcid': 'https://orcid.org/0000-0002-6405-365X'}, 'institutions': [], 'countries': [], 'is_corresponding': False, 'raw_author_name': 'Thomas Vidick', 'raw_affiliation_strings': [], 'affiliations': []}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5074369690', 'display_name': 'Danupon Nanongkai', 'orcid': 'https://orcid.org/0000-0003-4468-2675'}, 'institutions': [], 'countries': [], 'is_corresponding': False, 'raw_author_name': 'Danupon Nanongkai', 'raw_affiliation_strings': [], 'affiliations': []}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5021300666', 'display_name': 'Dimitris Achlioptas', 'orcid': 'https://orcid.org/0000-0003-2349-822X'}, 'institutions': [], 'countries': [], 'is_corresponding': False, 'raw_author_name': 'Dimitris Achlioptas', 'raw_affiliation_strings': [], 'affiliations': []}], 'institution_assertions': [], 'countries_distinct_count': 0, 'institutions_distinct_count': 0, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 0.0, 'has_fulltext': False, 'cited_by_count': 1, 'citation_normalized_percentile': {'value': 0.381187, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 61, 'max': 69}, 'biblio': {'volume': '49', 'issue': '5', 'first_page': 'STOC18', 'last_page': 'ii'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9841, '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.9841, '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/T12002', 'display_name': 'Computability, Logic, AI Algorithms', 'score': 0.9795, '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/T11567', 'display_name': 'semigroups and automata theory', 'score': 0.9701, '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'}}], 'keywords': [], 'concepts': [{'id': 'https://openalex.org/C161191863', 'wikidata': 'https://www.wikidata.org/wiki/Q199655', 'display_name': 'Library science', 'level': 1, 'score': 0.5104131}, {'id': 'https://openalex.org/C52119013', 'wikidata': 'https://www.wikidata.org/wiki/Q50637', 'display_name': 'Art history', 'level': 1, 'score': 0.4087351}, {'id': 'https://openalex.org/C142362112', 'wikidata': 'https://www.wikidata.org/wiki/Q735', 'display_name': 'Art', 'level': 0, 'score': 0.2924043}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.2543261}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1137/20n975154', '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': [{'display_name': 'Partnerships for the goals', 'score': 0.41, 'id': 'https://metadata.un.org/sdg/17'}], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 0, 'referenced_works': [], 'related_works': ['https://openalex.org/W658636438', 'https://openalex.org/W654893371', 'https://openalex.org/W617126653', 'https://openalex.org/W4389967401', 'https://openalex.org/W2748952813', 'https://openalex.org/W2739427100', 'https://openalex.org/W2070869476', 'https://openalex.org/W2039589765', 'https://openalex.org/W2010066730', 'https://openalex.org/W2001060508'], 'abstract_inverted_index': {'This': [0, 473, 877], 'issue': [1], 'of': [2, 17, 47, 69, 75, 79, 99, 117, 131, 151, 158, 164, 169, 187, 200, 209, 226, 273, 286, 324, 536, 584, 601, 624, 643, 656, 668, 677, 687, 692, 714, 720, 755, 780, 802, 816, 831], 'SICOMP': [3], 'contains': [4], '10': [5], 'specially': [6], 'selected': [7, 222], 'papers': [8, 34, 52, 224, 233], 'from': [9, 346, 497], 'the': [10, 41, 44, 48, 59, 64, 232, 258, 266, 274, 338, 362, 399, 411, 414, 426, 436, 475, 555, 574, 580, 630, 644, 666, 688, 693, 698, 712, 716, 728, 743, 752, 781, 800, 879], 'Fiftieth': [11], 'Annual': [12], 'ACM': [13], 'Symposium': [14], 'on': [15, 318, 435, 579, 673, 828], 'Theory': [16], 'Computing,': [18], 'otherwise': [19], 'known': [20, 315], 'as': [21, 326, 328], 'STOC': [22, 49], '2018,': [23], 'held': [24], 'June': [25], '25': [26], 'to': [27, 38, 63, 313, 320, 361, 372, 398, 628, 636], '29': [28], 'in': [29, 269, 367, 423, 513, 525, 593, 697, 742, 769, 836], 'Los': [30], 'Angeles,': [31], 'California.': [32], 'The': [33, 51, 71], 'here': [35], 'were': [36, 404], 'chosen': [37], 'represent': [39], 'both': [40, 884], 'excellence': [42], 'and': [43, 56, 61, 171, 216, 254, 282, 292, 305, 333, 354, 388, 425, 430, 455, 505, 570, 615, 708, 749, 786, 795, 812, 833, 867, 874, 888], 'broad': [45], 'range': [46], 'program.': [50], 'have': [53, 548], 'been': [54], 'revised': [55], 'extended': [57], 'by': [58, 682, 747, 799, 820], 'authors': [60, 412], 'subjected': [62], 'standard': [65], 'thorough': [66], 'reviewing': [67], 'process': [68], 'SICOMP.': [70], 'program': [72], 'committee': [73], 'consisted': [74], 'Dimitris': [76], 'Achlioptas': [77], '(University': [78, 98, 116, 130, 163, 208], 'California,': [80, 118], 'Santa': [81], 'Cruz),': [82], 'Dorit': [83], 'Aharonov': [84], '(Hebrew': [85], 'University),': [86, 95, 105, 123, 136, 140, 177, 195, 215], 'Susanne': [87], 'Albers': [88], '(Technical': [89], 'University': [90], 'Munich),': [91], 'Eric': [92], 'Allender': [93], '(Rutgers': [94], 'Sayan': [96], 'Bhattacharya': [97], 'Warwick),': [100], 'Richard': [101], 'Cole': [102], '(New': [103], 'York': [104], 'Vitaly': [106], 'Feldman': [107], '(Google': [108], 'Research),': [109], 'Uriel': [110], 'Feige': [111], '(Weizmann': [112], 'Institute),': [113], 'Sanjam': [114], 'Garg': [115, 457], 'Berkeley),': [119], 'Ashish': [120], 'Goel': [121], '(Stanford': [122, 176, 219], 'Parikshit': [124], 'Gopalan': [125], '(VMware),': [126], 'Monika': [127], 'Henzinger,': [128], 'chair': [129], 'Vienna),': [132], 'Giuseppe': [133], 'Italiano': [134], '(Luiss': [135], 'Robert': [137], 'Kleinberg': [138], '(Cornell': [139], 'Claire': [141], 'Matthieu': [142], '(École': [143], 'Normale': [144], 'Supérieure,': [145], 'CNRS),': [146], 'Ankur': [147], 'Moitra': [148], '(Massachusetts': [149], 'Institute': [150, 157, 186, 199], 'Technology),': [152, 188, 201], 'Danupon': [153], 'Nanongkai': [154], '(KTH': [155], 'Royal': [156], 'Technology,': [159, 172], 'Stockholm),': [160], 'Michał': [161], 'Pilipczuk': [162], 'Warsaw),': [165], 'Krzysztof': [166, 252], 'Pietrzak': [167], '(Institute': [168], 'Science': [170], 'Austria),': [173], 'Aaron': [174], 'Sidford': [175], 'Christian': [178], 'Sohler': [179], '(Universität': [180], 'zu': [181], 'Köln),': [182], 'Prasad': [183], 'Tetali': [184], '(Georgia': [185], 'Kunal': [189], 'Talwar': [190], '(Apple),': [191], 'Luca': [192], 'Trevisan': [193], '(Bocconi': [194], 'Thomas': [196], 'Vidick': [197], '(California': [198], 'Emo': [202], 'Welzl': [203], '(ETH': [204], 'Zurich),': [205], 'Philipp': [206], 'Woelfel': [207], 'Calgary),': [210], 'David': [211], 'Woodruff': [212], '(Carnegie': [213], 'Mellon': [214], 'Mary': [217], 'Wootters': [218], 'University).': [220], 'They': [221, 735, 808], '112': [223], 'out': [225], '416': [227], 'submissions.': [228], 'We': [229], 'briefly': [230], 'describe': [231], 'that': [234, 378, 390, 401, 420, 509, 540, 632, 649, 662, 737, 835], 'appear': [235], 'here.': [236], 'In': [237, 279, 341, 408, 441, 490, 553, 598, 690, 775, 848], '"Round': [238], 'Compression': [239], 'for': [240, 264, 406, 447, 462, 494, 518, 541, 558, 641, 660, 853, 864], 'Parallel': [241, 851], 'Matching': [242], 'Algorithms,"': [243], 'Artur': [244], 'Czumaj,': [245], 'Jakub': [246], 'Ła̧cki,': [247], 'Aleksander': [248], 'Ma̧dry,': [249], 'Slobodan': [250], 'Mitrović,': [251], 'Onak,': [253], 'Piotr': [255], 'Sankowski': [256], 'break': [257], '$O(\\log': [259], 'n)$': [260], 'round': [261], 'complexity': [262, 583, 713], 'bound': [263, 825], '2-approximating': [265], 'maximum': [267, 724], 'matching': [268], 'near-linear': [270], 'memory': [271], 'regime': [272], 'massively': [275], 'parallel': [276, 862, 881], 'computation': [277], 'model.': [278], '"Smooth': [280], 'Heaps': [281], 'a': [283, 296, 321, 330, 358, 459, 498, 519, 529, 590, 721, 732, 739, 765, 860], 'Dual': [284], 'View': [285], 'Self-Adjusting': [287], 'Data': [288, 561], 'Structures,"': [289], 'László': [290], 'Kozma': [291], 'Thatchaphol': [293], 'Saranurak': [294], 'show': [295, 508, 834], 'new': [297, 359], 'correspondence': [298], 'between': [299], 'self-adjusting': [300], 'binary': [301], 'search': [302], 'trees': [303, 757], '(BSTs)': [304], 'heaps.': [306], 'Using': [307], 'this': [308, 409, 537], 'connection': [309], 'they': [310], 'are': [311, 626], 'able': [312], 'transfer': [314], 'lower': [316, 577, 596], 'bounds': [317, 578], 'BSTs': [319], 'general': [322], 'model': [323], 'heaps': [325], 'well': [327], 'obtain': [329, 413], 'new,': [331], 'simple,': [332], 'efficient': [334], 'heap': [335], 'algorithm': [336, 863, 882], 'called': [337], '"smooth': [339], 'heap."': [340], '"Collusion': [342], 'Resistant': [343], 'Traitor': [344], 'Tracing': [345], 'Learning': [347], 'with': [348, 417, 438, 444, 467, 482, 723, 792, 805, 826, 870], 'Errors,"': [349], 'Rishab': [350], 'Goyal,': [351], 'Venkata': [352], 'Koppula,': [353], 'Brent': [355], 'Waters': [356], 'introduce': [357], 'approach': [360], 'traitor': [363, 368], 'tracing': [364, 369], 'problem.': [365], 'Informally,': [366], 'one': [370], 'aims': [371], 'devise': [373], 'an': [374, 608, 669, 810, 822], 'encryption': [375], 'scheme': [376, 416], 'such': [377, 389], 'decryption': [379, 393], 'can': [380, 394, 664], 'be': [381, 395], 'performed': [382], 'using': [383], '$n$': [384, 796], 'different': [385], 'private': [386], 'keys': [387], 'moreover': [391], 'any': [392], '"traced': [396], 'back"': [397], 'key(s)': [400], 'was': [402], 'or': [403], 'used': [405], 'it.': [407], 'paper': [410], 'first': [415, 476, 575, 880], 'ciphertext': [418], 'size': [419], 'grows': [421], 'polynomially': [422], '$\\log(n)$': [424], 'security': [427, 432], 'parameter': [428], '$\\lambda$': [429, 730, 763], 'whose': [431], 'is': [433, 474, 539, 731, 760, 764, 773, 878], 'based': [434], 'learning': [437], 'errors': [439], 'assumption.': [440], '"Pseudorandom': [442], 'Pseudo-distributions': [443], 'Near-Optimal': [445], 'Error': [446], 'Read-Once': [448], 'Branching': [449], 'Programs,"': [450], 'Mark': [451], 'Braverman,': [452], 'Gil': [453], 'Cohen,': [454], 'Sumegha': [456], 'construct': [458], 'hitting': [460], 'set': [461, 718], 'unrestricted': [463], 'read-once': [464], 'branching': [465], 'programs': [466, 791], 'seed': [468, 483], 'length': [469, 484], '$O(\\log^2n': [470, 485], '+': [471, 486, 843], '\\log(1/\\varepsilon))$.': [472], 'improvement': [477], 'since': [478], "Nisan's": [479], 'pseudorandom': [480], 'generator': [481], '\\log': [487, 653], 'n': [488], '\\log(1/\\varepsilon)$.': [489], '"Circuit': [491], 'Lower': [492, 563], 'Bounds': [493], 'Nondeterministic': [495], 'Quasi-Polytime': [496], 'New': [499], 'Easy': [500], 'Witness': [501], 'Lemma,"': [502], 'Cody': [503], 'Murray': [504], 'Ryan': [506], 'Williams': [507], 'if': [510], 'every': [511, 523, 542], 'problem': [512, 524], 'NP': [514, 526], 'has': [515, 528], 'polynomial-size': [516, 531], 'circuits': [517, 676], 'fixed': [520, 530, 543, 679], 'polynomial,': [521], 'then': [522], 'also': [527], 'witness.': [532], 'A': [533], 'specific': [534], 'consequence': [535], 'result': [538], '$k$,': [544], 'NQP': [545], 'does': [546], 'not': [547], '$n^{\\log^k': [549], 'n}$-size': [550], 'ACC$\\circ$THR': [551], 'circuits.': [552], '"Crossing': [554], 'Logarithmic': [556], 'Barrier': [557], 'Dynamic': [559], 'Boolean': [560, 586], 'Structure': [562], 'Bounds,"': [564], 'Kasper': [565], 'Green': [566], 'Larsen,': [567], 'Omri': [568], 'Weinstein,': [569], 'Huacheng': [571], 'Yu': [572], 'prove': [573, 736], 'superlogarithmic': [576], 'cell': [581], 'probe': [582], 'dynamic': [585], 'data': [587, 594], 'structure': [588, 595], 'problems,': [589], 'long-standing': [591], 'milestone': [592], 'bounds.': [597], '"Shadow': [599], 'Tomography': [600], 'Quantum': [602], 'States,"': [603], 'Scott': [604], 'Aaronson': [605], 'asks:': [606], 'Given': [607], 'unknown': [609], '$D$-dimensional': [610], 'quantum': [611], 'mixed': [612], 'state': [613], '$\\rho$': [614, 625, 635, 657], 'two-outcome': [616], 'measurements': [617], '$E_1,': [618], '\\ldots,': [619], 'E_M$,': [620], 'how': [621], 'many': [622], 'copies': [623, 655, 686], 'needed': [627], 'estimate': [629], 'probability': [631], '$E_i$': [633], 'accepts': [634], 'within': [637], 'additive': [638], 'error': [639], '$\\varepsilon$,': [640], 'each': [642], '$M$': [645], 'measurements?': [646], 'He': [647], 'shows': [648], '$O(\\varepsilon^{-4}': [650], '\\log^4': [651], 'M': [652], 'D)$': [654], 'suffice,': [658], 'implying,': [659], 'example,': [661], 'we': [663], 'learn': [665], 'behavior': [667], 'arbitrary': [670], '$n$-qubit': [671], 'state,': [672], 'all': [674], 'accepting/rejecting': [675], 'some': [678], 'polynomial': [680, 719], 'size,': [681], 'measuring': [683], 'only': [684], '$n^{O(1)}$': [685], 'state.': [689], '"Inapproximability': [691], 'Independent': [694], 'Set': [695], 'Polynomial': [696], 'Complex': [699], 'Plane,"': [700], 'Ivona': [701], 'Bezáková,': [702], 'Andreas': [703], 'Galanis,': [704], 'Leslie': [705], 'Ann': [706], 'Goldberg,': [707], 'Daniel': [709, 784], 'Štefankovič': [710], 'study': [711], 'approximating': [715], 'independent': [717], 'graph': [722], 'degree': [725], '$\\Delta$': [726], 'when': [727], 'activity': [729], 'complex': [733, 744], 'number.': [734], 'outside': [738], 'cardioid-shaped': [740], 'region': [741], 'plane': [745], 'identified': [746], 'Peters': [748], 'Regts,': [750], 'wherein': [751], 'occupation': [753], 'ratios': [754], '$\\Delta$-regular': [756], 'converge,': [758], 'approximation': [759], '$\\#$P-hard': [761], '(unless': [762], 'positive': [766], 'real': [767], 'number,': [768], 'which': [770], 'case': [771], 'it': [772], 'NP-hard).': [774], '"A': [776], 'Friendly': [777], 'Smoothed': [778], 'Analysis': [779], 'Simplex': [782], 'Method,"': [783], 'Dadush': [785], 'Sophie': [787], 'Huiberts': [788], 'consider': [789], 'linear': [790, 886], '$d$': [793], 'variables': [794], 'constraints,': [797], 'smoothed': [798], 'addition': [801], 'Gaussian': [803], 'noise': [804], 'variance': [806], '$\\sigma^2$.': [807], 'provide': [809], 'improved': [811, 823], 'greatly': [813], 'simplified': [814], 'analysis': [815], 'shadow': [817, 824], 'simplex': [818], 'methods': [819], 'combining': [821], 'improvements': [827], 'algorithmic': [829], 'techniques': [830], 'Vershynin': [832], 'expectation': [837], '$O(d^2': [838], '\\sqrt{\\log': [839], 'n}': [840], '\\,': [841], '\\sigma^{-2}': [842], 'd^3': [844], '\\log^{3/2}n)$': [845], 'pivots': [846], 'suffice.': [847], '"Nearly': [849], 'Work-Efficient': [850], 'Algorithm': [852], 'Digraph': [854], 'Reachability,"': [855], 'Jeremy': [856], 'T.': [857], 'Fineman': [858], 'presents': [859], 'randomized': [861], 'digraph': [865], 'reachability': [866], 'related': [868], 'problems': [869], 'expected': [871], 'work': [872, 887], '$\\tilde{O}(m)$': [873], 'span': [875], '$\\tilde{O}(n^{2/3})$.': [876], 'having': [883], 'nearly': [885], 'strongly': [889], 'sublinear': [890], 'span.': [891]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W3095276197', 'counts_by_year': [{'year': 2024, 'cited_by_count': 1}], 'updated_date': '2024-12-10T05:19:25.881030', 'created_date': '2020-11-09'}