Publication Information

{'id': 'https://openalex.org/W2198255326', 'doi': 'https://doi.org/10.1145/3015762', 'title': 'Lopsidependency in the Moser-Tardos Framework', 'display_name': 'Lopsidependency in the Moser-Tardos Framework', 'publication_year': 2016, 'publication_date': '2016-12-21', 'ids': {'openalex': 'https://openalex.org/W2198255326', 'doi': 'https://doi.org/10.1145/3015762', 'mag': '2198255326'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/3015762', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S137348503', 'display_name': 'ACM Transactions on Algorithms', 'issn_l': '1549-6325', 'issn': ['1549-6325', '1549-6333'], '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': False, 'oa_status': 'closed', 'oa_url': None, 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5101783327', 'display_name': 'David G. Harris', 'orcid': 'https://orcid.org/0000-0002-3021-3555'}, 'institutions': [{'id': 'https://openalex.org/I66946132', 'display_name': 'University of Maryland, College Park', 'ror': 'https://ror.org/047s2c258', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I66946132']}], 'countries': ['US'], 'is_corresponding': True, 'raw_author_name': 'David G. Harris', 'raw_affiliation_strings': ['University of Maryland'], 'affiliations': [{'raw_affiliation_string': 'University of Maryland', 'institution_ids': ['https://openalex.org/I66946132']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 1, 'corresponding_author_ids': ['https://openalex.org/A5101783327'], 'corresponding_institution_ids': ['https://openalex.org/I66946132'], 'apc_list': None, 'apc_paid': None, 'fwci': 2.71, 'has_fulltext': False, 'cited_by_count': 26, 'citation_normalized_percentile': {'value': 0.925295, 'is_in_top_1_percent': False, 'is_in_top_10_percent': True}, 'cited_by_percentile_year': {'min': 92, 'max': 93}, 'biblio': {'volume': '13', 'issue': '1', 'first_page': '1', 'last_page': '26'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9998, '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.9998, '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/T11303', 'display_name': 'Bayesian Modeling and Causal Inference', 'score': 0.9971, '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/T12056', 'display_name': 'Markov Chains and Monte Carlo Methods', 'score': 0.997, 'subfield': {'id': 'https://openalex.org/subfields/2613', 'display_name': 'Statistics and Probability'}, 'field': {'id': 'https://openalex.org/fields/26', 'display_name': 'Mathematics'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/generality', 'display_name': 'Generality', 'score': 0.49850154}, {'id': 'https://openalex.org/keywords/statement', 'display_name': 'Statement (logic)', 'score': 0.4585585}], 'concepts': [{'id': 'https://openalex.org/C136197465', 'wikidata': 'https://www.wikidata.org/wiki/Q1729295', 'display_name': 'Variety (cybernetics)', 'level': 2, 'score': 0.789768}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.5710722}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.5445415}, {'id': 'https://openalex.org/C34388435', 'wikidata': 'https://www.wikidata.org/wiki/Q2267362', 'display_name': 'Bounded function', 'level': 2, 'score': 0.5328235}, {'id': 'https://openalex.org/C2780767217', 'wikidata': 'https://www.wikidata.org/wiki/Q5532421', 'display_name': 'Generality', 'level': 2, 'score': 0.49850154}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.46153152}, {'id': 'https://openalex.org/C2777026412', 'wikidata': 'https://www.wikidata.org/wiki/Q2684591', 'display_name': 'Statement (logic)', 'level': 2, 'score': 0.4585585}, {'id': 'https://openalex.org/C182365436', 'wikidata': 'https://www.wikidata.org/wiki/Q50701', 'display_name': 'Variable (mathematics)', 'level': 2, 'score': 0.43228433}, {'id': 'https://openalex.org/C2780428219', 'wikidata': 'https://www.wikidata.org/wiki/Q16952335', 'display_name': 'Cover (algebra)', 'level': 2, 'score': 0.41804343}, {'id': 'https://openalex.org/C49937458', 'wikidata': 'https://www.wikidata.org/wiki/Q2599292', 'display_name': 'Probabilistic logic', 'level': 2, 'score': 0.41146117}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.3274524}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.325181}, {'id': 'https://openalex.org/C105795698', 'wikidata': 'https://www.wikidata.org/wiki/Q12483', 'display_name': 'Statistics', 'level': 1, 'score': 0.0869337}, {'id': 'https://openalex.org/C15744967', 'wikidata': 'https://www.wikidata.org/wiki/Q9418', 'display_name': 'Psychology', 'level': 0, '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/C542102704', 'wikidata': 'https://www.wikidata.org/wiki/Q183257', 'display_name': 'Psychotherapist', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C78519656', 'wikidata': 'https://www.wikidata.org/wiki/Q101333', 'display_name': 'Mechanical engineering', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C17744445', 'wikidata': 'https://www.wikidata.org/wiki/Q36442', 'display_name': 'Political science', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C199539241', 'wikidata': 'https://www.wikidata.org/wiki/Q7748', 'display_name': 'Law', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C127413603', 'wikidata': 'https://www.wikidata.org/wiki/Q11023', 'display_name': 'Engineering', 'level': 0, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/3015762', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S137348503', 'display_name': 'ACM Transactions on Algorithms', 'issn_l': '1549-6325', 'issn': ['1549-6325', '1549-6333'], '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}], 'best_oa_location': None, 'sustainable_development_goals': [], 'grants': [{'funder': 'https://openalex.org/F4320306076', 'funder_display_name': 'National Science Foundation', 'award_id': 'CNS 1010789 and CCF 1422569'}], 'datasets': [], 'versions': [], 'referenced_works_count': 23, 'referenced_works': ['https://openalex.org/W1776544432', 'https://openalex.org/W1983085249', 'https://openalex.org/W2000171675', 'https://openalex.org/W2007351870', 'https://openalex.org/W2017205387', 'https://openalex.org/W2042125214', 'https://openalex.org/W2047290604', 'https://openalex.org/W2051336598', 'https://openalex.org/W2063241141', 'https://openalex.org/W2066969286', 'https://openalex.org/W2072870176', 'https://openalex.org/W2072991076', 'https://openalex.org/W2085708731', 'https://openalex.org/W2104180013', 'https://openalex.org/W2109693504', 'https://openalex.org/W2118882118', 'https://openalex.org/W2119305988', 'https://openalex.org/W2137916360', 'https://openalex.org/W2156584294', 'https://openalex.org/W2510181305', 'https://openalex.org/W2963097814', 'https://openalex.org/W310689670', 'https://openalex.org/W4299975359'], 'related_works': ['https://openalex.org/W988368302', 'https://openalex.org/W4290792893', 'https://openalex.org/W2612287894', 'https://openalex.org/W2610071704', 'https://openalex.org/W2341733084', 'https://openalex.org/W2136053165', 'https://openalex.org/W2113767142', 'https://openalex.org/W2042726902', 'https://openalex.org/W2018828049', 'https://openalex.org/W1978042415'], 'abstract_inverted_index': {'The': [0, 43], 'Lopsided': [1, 288], 'Lovász': [2, 274], 'Local': [3, 275], 'Lemma': [4, 276], '(LLLL)': [5], 'is': [6, 51, 117, 137, 154, 178, 213, 218, 252], 'a': [7, 16, 26, 38, 106, 168, 194, 256, 268, 279, 284], 'powerful': [8], 'probabilistic': [9], 'principle': [10, 23], 'that': [11, 79], 'has': [12, 33], 'been': [13, 35, 63, 86], 'used': [14], 'in': [15, 124, 144, 164, 189, 198, 302, 306], 'variety': [17, 39, 59, 169], 'of': [18, 40, 46, 56, 60, 161, 170, 185, 286], 'combinatorial': [19], 'constructions.': [20], 'While': [21, 263], 'this': [22, 216], 'began': [24], 'as': [25, 148], 'general': [27], 'statement': [28], 'about': [29], 'probability': [30], 'spaces,': [31], 'it': [32, 140, 153, 226], 'recently': [34], 'transformed': [36], 'into': [37], 'polynomial-time': [41], 'algorithms.': [42, 174], 'resampling': [44], 'algorithm': [45, 112, 259, 271, 282, 300, 310], 'Moser': [47, 264], 'and': [48, 76, 96, 99, 173, 265, 277], 'Tardos': [49, 266], '[2010]': [50], 'the': [52, 66, 68, 110, 120, 132, 145, 149, 162, 261, 273, 287, 296, 308], 'most': [53], 'well-known': [54], 'example': [55], 'this.': [57], 'A': [58, 175], 'criteria': [61, 78], 'have': [62, 85], 'shown': [64, 73, 87, 188], 'for': [65, 109, 179, 260, 272, 283], 'LLLL;': [67, 151], 'strongest': [69], 'possible': [70, 138], 'criterion': [71, 108, 116], 'was': [72], 'by': [74, 88, 315], 'Shearer,': [75], 'other': [77], 'are': [80], 'easier': [81], 'to': [82, 113, 157, 227, 294], 'use': [83], 'computationally': [84], 'Bissacot': [89], 'et': [90, 101, 191], 'al.': [91, 102, 192], '[2011],': [92, 98, 193], 'Pegden': [93], '[2014],': [94], 'Kolipaka': [95, 100], 'Szegedy': [97], '[2012].': [103], 'We': [104, 166, 254], 'show': [105, 167], 'new': [107, 171, 257, 299], 'Moser-Tardos': [111], 'converge.': [114], 'This': [115, 136], 'stronger': [118, 249, 318], 'than': [119, 131], 'LLLL': [121, 163, 319], 'criterion,': [122], 'and,': [123], 'fact,': [125], 'can': [126, 246], 'yield': [127], 'better': [128], 'results': [129], 'even': [130], 'full': [133], 'Shearer': [134], 'criterion.': [135, 320], 'because': [139], 'does': [141], 'not': [142, 292], 'apply': [143], 'same': [146], 'generality': [147], 'original': [150], 'yet,': [152], 'strong': [155], 'enough': [156], 'cover': [158], 'many': [159], 'applications': [160], 'combinatorics.': [165], 'bounds': [172], 'noteworthy': [176], 'application': [177], 'k': [180, 195, 206, 210, 222, 231, 236, 238, 239, 243, 251], '-SAT,': [181], 'with': [182], 'bounded': [183], 'occurrences': [184], 'variables.': [186], 'As': [187], 'Gebauer': [190], '-SAT': [196], 'instance': [197], 'which': [199, 245, 307], 'every': [200], 'variable': [201], 'appears': [202], 'L': [203, 228], '≤': [204, 229], '2/': [205, 230, 242], '+1': [207, 232], 'e': [208], '(': [209], '+1)': [211], 'times,': [212], 'satisfiable.': [214], 'Although': [215], 'bound': [217], 'asymptotically': [219], 'tight': [220], '(in': [221], '),': [223], 'we': [224], 'improve': [225], '(1': [233], '−': [234, 241], '1/': [235], ')': [237], '−1': [240], ',': [244], 'be': [247], 'significantly': [248], 'when': [250], 'small.': [253], 'introduce': [255], 'parallel': [258, 270], 'LLLL.': [262], 'described': [267, 278], 'simple': [269, 280], 'sequential': [281, 309], 'form': [285], 'Lemma,': [289], 'they': [290], 'were': [291], 'able': [293], 'combine': [295], 'two.': [297], 'Our': [298], 'applies': [301], 'nearly': [303], 'all': [304], 'settings': [305, 313], 'works—this': [311], 'includes': [312], 'covered': [314], 'our': [316], 'new,': [317]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2198255326', 'counts_by_year': [{'year': 2024, 'cited_by_count': 1}, {'year': 2022, 'cited_by_count': 2}, {'year': 2021, 'cited_by_count': 3}, {'year': 2020, 'cited_by_count': 5}, {'year': 2019, 'cited_by_count': 3}, {'year': 2018, 'cited_by_count': 1}, {'year': 2017, 'cited_by_count': 6}, {'year': 2016, 'cited_by_count': 2}, {'year': 2015, 'cited_by_count': 3}], 'updated_date': '2025-01-04T16:47:10.006056', 'created_date': '2016-06-24'}