Publication Information

{'id': 'https://openalex.org/W2161185760', 'doi': 'https://doi.org/10.1109/focs.2012.58', 'title': 'Faster SDP Hierarchy Solvers for Local Rounding Algorithms', 'display_name': 'Faster SDP Hierarchy Solvers for Local Rounding Algorithms', 'publication_year': 2012, 'publication_date': '2012-10-01', 'ids': {'openalex': 'https://openalex.org/W2161185760', 'doi': 'https://doi.org/10.1109/focs.2012.58', 'mag': '2161185760'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1109/focs.2012.58', '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': True, 'oa_status': 'green', 'oa_url': 'https://arxiv.org/pdf/1207.4372', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5068388812', 'display_name': 'Venkatesan Guruswami', 'orcid': 'https://orcid.org/0000-0001-7926-3396'}, 'institutions': [{'id': 'https://openalex.org/I74973139', 'display_name': 'Carnegie Mellon University', 'ror': 'https://ror.org/05x2bcf33', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I74973139']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Venkatesan Guruswami', 'raw_affiliation_strings': ['Computer Science Department, Carnegie Mellon University, USA'], 'affiliations': [{'raw_affiliation_string': 'Computer Science Department, Carnegie Mellon University, USA', 'institution_ids': ['https://openalex.org/I74973139']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5086919065', 'display_name': 'Ali Kemal Sinop', 'orcid': 'https://orcid.org/0000-0001-6550-6027'}, 'institutions': [{'id': 'https://openalex.org/I20089843', 'display_name': 'Princeton University', 'ror': 'https://ror.org/00hx57361', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I20089843']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Ali Kemal Sinop', 'raw_affiliation_strings': ['Center for Computational Intractability, Department of Computer Science, Princeton University, USA'], 'affiliations': [{'raw_affiliation_string': 'Center for Computational Intractability, Department of Computer Science, Princeton University, USA', 'institution_ids': ['https://openalex.org/I20089843']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 2, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 1.796, 'has_fulltext': True, 'fulltext_origin': 'ngrams', 'cited_by_count': 20, 'citation_normalized_percentile': {'value': 0.804212, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 90, 'max': 91}, 'biblio': {'volume': None, 'issue': None, 'first_page': '197', 'last_page': '206'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10054', 'display_name': 'Parallel Computing and Optimization Techniques', 'score': 0.9994, 'subfield': {'id': 'https://openalex.org/subfields/1708', 'display_name': 'Hardware and Architecture'}, '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/T10054', 'display_name': 'Parallel Computing and Optimization Techniques', 'score': 0.9994, 'subfield': {'id': 'https://openalex.org/subfields/1708', 'display_name': 'Hardware and Architecture'}, '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/T11697', 'display_name': 'Numerical Methods and Algorithms', 'score': 0.9993, '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/T11522', 'display_name': 'VLSI and FPGA Design Techniques', 'score': 0.999, 'subfield': {'id': 'https://openalex.org/subfields/2208', 'display_name': 'Electrical and Electronic Engineering'}, 'field': {'id': 'https://openalex.org/fields/22', 'display_name': 'Engineering'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/rounding', 'display_name': 'Rounding', 'score': 0.89009535}], 'concepts': [{'id': 'https://openalex.org/C136625980', 'wikidata': 'https://www.wikidata.org/wiki/Q663208', 'display_name': 'Rounding', 'level': 2, 'score': 0.89009535}, {'id': 'https://openalex.org/C31170391', 'wikidata': 'https://www.wikidata.org/wiki/Q188619', 'display_name': 'Hierarchy', 'level': 2, 'score': 0.70790404}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.6973914}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.5648009}, {'id': 'https://openalex.org/C80444323', 'wikidata': 'https://www.wikidata.org/wiki/Q2878974', 'display_name': 'Theoretical computer science', 'level': 1, 'score': 0.37022763}, {'id': 'https://openalex.org/C34447519', 'wikidata': 'https://www.wikidata.org/wiki/Q179522', 'display_name': 'Market economy', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C162324750', 'wikidata': 'https://www.wikidata.org/wiki/Q8134', 'display_name': 'Economics', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C111919701', 'wikidata': 'https://www.wikidata.org/wiki/Q9135', 'display_name': 'Operating system', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 2, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1109/focs.2012.58', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/1207.4372', 'pdf_url': 'https://arxiv.org/pdf/1207.4372', '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://arxiv.org/abs/1207.4372', 'pdf_url': 'https://arxiv.org/pdf/1207.4372', '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}, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 26, 'referenced_works': ['https://openalex.org/W129224317', 'https://openalex.org/W1524253248', 'https://openalex.org/W1558498035', 'https://openalex.org/W1590002045', 'https://openalex.org/W1593162480', 'https://openalex.org/W1754192177', 'https://openalex.org/W1886138972', 'https://openalex.org/W1947552815', 'https://openalex.org/W1997672673', 'https://openalex.org/W2028932986', 'https://openalex.org/W2049143039', 'https://openalex.org/W2071588464', 'https://openalex.org/W2077397558', 'https://openalex.org/W2089135543', 'https://openalex.org/W2095315734', 'https://openalex.org/W2100440346', 'https://openalex.org/W2106264302', 'https://openalex.org/W2148012376', 'https://openalex.org/W2151395725', 'https://openalex.org/W2166536886', 'https://openalex.org/W2249739104', 'https://openalex.org/W2473711771', 'https://openalex.org/W2796987707', 'https://openalex.org/W2949580236', 'https://openalex.org/W4212899103', 'https://openalex.org/W4293860921'], 'related_works': ['https://openalex.org/W4391375266', 'https://openalex.org/W4220780102', 'https://openalex.org/W3196334750', 'https://openalex.org/W2748952813', 'https://openalex.org/W2410881844', 'https://openalex.org/W2357551824', 'https://openalex.org/W2116281088', 'https://openalex.org/W2016668641', 'https://openalex.org/W2004257129', 'https://openalex.org/W1502401885'], 'abstract_inverted_index': {'Convex': [0], 'relaxations': [1], 'based': [2, 76, 186, 197, 349], 'on': [3, 77, 143, 187, 198, 283], 'different': [4], 'hierarchies': [5], 'of': [6, 24, 31, 40, 72, 87, 102, 133, 146, 190, 252, 278, 293, 338, 360, 376], 'linear/semi-definite': [7], 'programs': [8, 354], 'have': [9], 'been': [10], 'used': [11, 367], 'recently': [12], 'to': [13, 112, 158, 169, 372], 'devise': [14], 'approximation': [15, 22], 'algorithms': [16, 26, 74, 168, 185], 'for': [17, 220, 270, 352], 'various': [18], 'optimization': [19], 'problems.': [20], 'The': [21, 123, 328], 'guarantee': [23, 260], 'these': [25, 73], 'improves': [27], 'with': [28, 362], 'the': [29, 35, 38, 46, 49, 62, 88, 114, 130, 134, 147, 171, 178, 191, 248, 253, 276], 'number': [30, 277], 'rounds': [32, 189, 201], 'r': [33, 188], 'in': [34, 117, 120, 125, 150, 174, 205, 232, 261, 296, 299, 322, 332, 341, 368, 379], 'hierarchy,': [36], 'though': [37], 'complexity': [39], 'solving': [41], '(or': [42], 'even': [43], 'writing': [44], 'down': [45], 'solution': [47, 90, 135], 'for)': [48], "r'th": [50, 249], 'level': [51], 'program': [52], 'grows': [53], 'as': [54, 177, 225], 'n': [55, 60, 93, 103, 159, 180, 233, 262], '<sup': [56, 94, 98, 104, 160, 164, 181, 234, 238, 263, 267, 301, 305], 'xmlns:mml="http://www.w3.org/1998/Math/MathML"': [57, 95, 99, 105, 161, 165, 182, 216, 235, 239, 245, 264, 268, 302, 306, 312], 'xmlns:xlink="http://www.w3.org/1999/xlink">Ω(r)</sup>': [58, 106], 'where': [59, 242, 273], 'is': [61, 128, 136, 247, 275, 285, 344, 366], 'input': [63], 'size.': [64, 122], 'In': [65, 194], 'this': [66, 127], 'work,': [67, 334], 'we': [68], 'observe': [69], 'that': [70, 81, 129, 355, 383], 'many': [71, 175], 'are': [75], 'local': [78, 385], 'rounding': [79, 386], 'procedures': [80], 'only': [82], 'use': [83], 'a': [84, 139, 151, 258, 323, 358, 369, 374], 'small': [85, 229], 'part': [86], 'SDP': [89], '(of': [91], 'size': [92, 294], 'xmlns:xlink="http://www.w3.org/1999/xlink">O(1)</sup>': [96, 162, 236, 265, 307], '2': [97, 163, 237], 'xmlns:xlink="http://www.w3.org/1999/xlink">O(r)</sup>': [100, 166, 183, 240, 269], 'instead': [101], ').': [107], 'We': [108, 316], 'give': [109], 'an': [110, 290, 345], 'algorithm': [111, 321, 348], 'find': [113, 289, 373], 'requisite': [115], 'portion': [116, 132], 'time': [118, 167, 184, 308], 'polynomial': [119, 206, 281], 'its': [121], 'challenge': [124], 'achieving': [126], 'required': [131], 'not': [137], 'fixed': [138], 'priori': [140], 'but': [141], 'depends': [142], 'other': [144], 'parts': [145], 'solution,': [148], 'sometimes': [149], 'complicated': [152], 'iterative': [153], 'manner.': [154], 'Our': [155], 'solver': [156], 'leads': [157], 'obtain': [170], 'same': [172], 'guarantees': [173, 196], 'cases': [176], 'earlier': [179], 'Lasserre': [192], 'hierarchy.': [193], 'particular,': [195], 'O(log': [199], 'n)': [200], 'can': [202, 211, 356], 'be': [203, 337], 'realized': [204], 'time.': [207], 'For': [208], 'instance,': [209], 'one': [210], '(i)': [212], 'get': [213], 'O(1/λ': [214], '<sub': [215, 244, 311], 'xmlns:xlink="http://www.w3.org/1999/xlink">r</sub>': [217, 246], ')': [218, 304], 'approximations': [219], 'graph': [221], 'partitioning': [222], 'problems': [223], 'such': [224], 'minimum': [226], 'bisection': [227], 'and': [228, 287, 318], 'set': [230, 292], 'expansion': [231], 'time,': [241], 'λ': [243, 310], 'smallest': [250], 'eigenvalue': [251], "graph's": [254], 'normalized': [255], 'Laplacian;': [256], '(ii)': [257], 'similar': [259], 'k': [266, 274, 284], 'Unique': [271], 'Games': [272], 'labels': [279], '(the': [280], 'dependence': [282], 'new);': [286], '(iii)': [288], 'independent': [291, 339], 'Ω(n)': [295], '3-colorable': [297], 'graphs': [298], '(n2': [300], 'xmlns:xlink="http://www.w3.org/1999/xlink">r</sup>': [303], 'provided': [309], 'xmlns:xlink="http://www.w3.org/1999/xlink">n-r</sub>': [313], '<;': [314], '17/16.': [315], 'develop': [317], 'describe': [319], 'our': [320, 333], 'fairly': [324], 'general': [325], 'abstract': [326], 'framework.': [327], 'main': [329], 'technical': [330], 'tool': [331], 'which': [335], 'might': [336], 'interest': [340], 'convex': [342, 353, 381], 'optimization,': [343], 'efficient': [346], 'ellipsoid': [347], 'separation': [350], 'oracle': [351], 'output': [357], 'certificate': [359], 'infeasibility': [361], 'restricted': [363], 'support.': [364], 'This': [365], 'recursive': [370], 'manner': [371], 'sequence': [375], 'consistent': [377], 'points': [378], 'nested': [380], 'bodies': [382], '"fools"': [384], 'algorithms.': [387]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2161185760', 'counts_by_year': [{'year': 2022, 'cited_by_count': 1}, {'year': 2021, 'cited_by_count': 3}, {'year': 2019, 'cited_by_count': 3}, {'year': 2018, 'cited_by_count': 1}, {'year': 2016, 'cited_by_count': 2}, {'year': 2015, 'cited_by_count': 3}, {'year': 2014, 'cited_by_count': 2}, {'year': 2013, 'cited_by_count': 5}], 'updated_date': '2024-12-14T06:19:28.175360', 'created_date': '2016-06-24'}