{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:30:14Z","timestamp":1750307414528,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2010,6,5]],"date-time":"2010-06-05T00:00:00Z","timestamp":1275696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2010,6,5]]},"DOI":"10.1145\/1806689.1806712","type":"proceedings-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T12:37:34Z","timestamp":1276000654000},"page":"151-160","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A quantum lov\u00e1sz local lemma"],"prefix":"10.1145","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[{"name":"University of Latvia, Riga, Latvia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julia","family":"Kempe","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Or","family":"Sattath","sequence":"additional","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,6,5]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-04-00464-3"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"e_1_3_2_1_3_1","volume-title":"The probabilistic method","author":"Alon N.","year":"2004","unstructured":"N. Alon and J.H. Spencer . The probabilistic method . Wiley--Interscience , 2004 . N. Alon and J.H. Spencer. The probabilistic method. Wiley--Interscience, 2004."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1178243286"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"e_1_3_2_1_6_1","volume-title":"On the complexity of computing Zero-Error and Holevo capacity of quantum channels. Arxiv preprint arXiv:0709.2090","author":"Beigi S.","year":"2007","unstructured":"S. Beigi and P.W. Shor . On the complexity of computing Zero-Error and Holevo capacity of quantum channels. Arxiv preprint arXiv:0709.2090 , 2007 . S. Beigi and P.W. Shor. On the complexity of computing Zero-Error and Holevo capacity of quantum channels. Arxiv preprint arXiv:0709.2090, 2007."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"Bollob\u00e1s B.","year":"2001","unstructured":"B. Bollob\u00e1s . Random Graphs . Cambridge University Press , 2 edition, 2001 . B. Bollob\u00e1s. Random Graphs. Cambridge University Press, 2 edition, 2001."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1006"},{"key":"e_1_3_2_1_9_1","volume-title":"Efficient algorithm for a quantum analogue of 2-SAT. Arxiv preprint quant-ph\/0602108","author":"Bravyi S.","year":"2006","unstructured":"S. Bravyi . Efficient algorithm for a quantum analogue of 2-SAT. Arxiv preprint quant-ph\/0602108 , 2006 . S. Bravyi. Efficient algorithm for a quantum analogue of 2-SAT. Arxiv preprint quant-ph\/0602108, 2006."},{"key":"e_1_3_2_1_10_1","first-page":"482","volume-title":"Innovations in Computer Science","author":"Bravyi S.","year":"2010","unstructured":"S. Bravyi , C. Moore , and A. Russell . Bounds on the quantum satisfibility threshold . Innovations in Computer Science , pages 482 -- 489 , 2010 . S. Bravyi, C. Moore, and A. Russell. Bounds on the quantum satisfibility threshold. Innovations in Computer Science, pages 482--489, 2010."},{"key":"e_1_3_2_1_11_1","volume-title":"Complexity of stoquastic frustration-free hamiltonians. Arxiv preprint arXiv:0806.1746","author":"Bravyi S.","year":"2008","unstructured":"S. Bravyi and B. Terhal . Complexity of stoquastic frustration-free hamiltonians. Arxiv preprint arXiv:0806.1746 , 2008 . S. Bravyi and B. Terhal. Complexity of stoquastic frustration-free hamiltonians. Arxiv preprint arXiv:0806.1746, 2008."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267789"},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the 11th Symposium on Discrete Algorithms, 17:30--39","author":"Czumaj A.","year":"2000","unstructured":"A. Czumaj and C. Scheideler . Coloring non-uniform hypergraphs: A new algorithmic approach to the general Lovasz local lemma . In Proceedings of the 11th Symposium on Discrete Algorithms, 17:30--39 , 2000 . A. Czumaj and C. Scheideler. Coloring non-uniform hypergraphs: A new algorithmic approach to the general Lovasz local lemma. In Proceedings of the 11th Symposium on Discrete Algorithms, 17:30--39, 2000."},{"key":"e_1_3_2_1_14_1","volume-title":"A new upper bound for 3-SAT. Arxiv preprint arXiv:0807.3600","author":"Diaz J.","year":"2008","unstructured":"J. Diaz , L. Kirousis , D. Mitsche , and X. Perez-Gimenez . A new upper bound for 3-SAT. Arxiv preprint arXiv:0807.3600 , 2008 . J. Diaz, L. Kirousis, D. Mitsche, and X. Perez-Gimenez. A new upper bound for 3-SAT. Arxiv preprint arXiv:0807.3600, 2008."},{"key":"e_1_3_2_1_15_1","volume-title":"Graph Theory (Graduate Texts in Mathematics)","author":"Diestel R.","year":"1997","unstructured":"R. Diestel . Graph Theory (Graduate Texts in Mathematics) . Springer Heidelberg , 1997 . R. Diestel. Graph Theory (Graduate Texts in Mathematics). Springer Heidelberg, 1997."},{"key":"e_1_3_2_1_16_1","volume-title":"Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finite sets, 2:609--627","author":"Erdos P.","year":"1975","unstructured":"P. Erdos and L. Lovasz . Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finite sets, 2:609--627 , 1975 . P. Erdos and L. Lovasz. Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finite sets, 2:609--627, 1975."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"e_1_3_2_1_18_1","unstructured":"L. Fortnow. A Kolmogorov Complexity Proof of the Lovasz Local Lemma. http:\/\/bit.ly\/AsHlm 2009.  L. Fortnow. A Kolmogorov Complexity Proof of the Lovasz Local Lemma. http:\/\/bit.ly\/AsHlm 2009."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/645721.663723"},{"key":"e_1_3_2_1_21_1","volume-title":"The satisfiability threshold of random 3-SAT is at least 3.52. Arxiv preprint math\/0310193","author":"Hajiaghayi M.T.","year":"2003","unstructured":"M.T. Hajiaghayi and G.B. Sorkin . The satisfiability threshold of random 3-SAT is at least 3.52. Arxiv preprint math\/0310193 , 2003 . M.T. Hajiaghayi and G.B. Sorkin. The satisfiability threshold of random 3-SAT is at least 3.52. Arxiv preprint math\/0310193, 2003."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(04)00462-7"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.264.5163.1297"},{"key":"e_1_3_2_1_26_1","volume-title":"Linear algebra and geometry","author":"Kostrikin A.I.","year":"1997","unstructured":"A.I. Kostrikin . Linear algebra and geometry . Taylor & Francis , 1997 . A.I. Kostrikin. Linear algebra and geometry. Taylor & Francis, 1997."},{"key":"e_1_3_2_1_27_1","volume-title":"On product, generic and random generic quantum satisfiability. Arxiv preprint arXiv:0910.2058","author":"Laumann C.R.","year":"2009","unstructured":"C.R. Laumann , A.M. Lauchli , R. Moessner , A. Scardicchio , and S. L Sondhi . On product, generic and random generic quantum satisfiability. Arxiv preprint arXiv:0910.2058 , 2009 . C.R. Laumann, A.M. Lauchli, R. Moessner, A. Scardicchio, and S. L Sondhi. On product, generic and random generic quantum satisfiability. Arxiv preprint arXiv:0910.2058, 2009."},{"key":"e_1_3_2_1_28_1","volume-title":"Phase transitions and random quantum satisfiability. Arxiv preprint arXiv:0903.1904","author":"Laumann C.R.","year":"2009","unstructured":"C.R. Laumann , R. Moessner , A. Scardicchio , and S.L. Sondhi . Phase transitions and random quantum satisfiability. Arxiv preprint arXiv:0903.1904 , 2009 . C.R. Laumann, R. Moessner, A. Scardicchio, and S.L. Sondhi. Phase transitions and random quantum satisfiability. Arxiv preprint arXiv:0903.1904, 2009."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_40"},{"key":"e_1_3_2_1_30_1","volume-title":"The complexity of the consistency and n-representability problems for quantum states. Arxiv preprint arXiv:0712.3041","author":"Liu Y.K.","year":"2007","unstructured":"Y.K. Liu . The complexity of the consistency and n-representability problems for quantum states. Arxiv preprint arXiv:0712.3041 , 2007 . Y.K. Liu. The complexity of the consistency and n-representability problems for quantum states. Arxiv preprint arXiv:0712.3041, 2007."},{"key":"e_1_3_2_1_31_1","volume-title":"Manuscript","author":"Mani-Levitska P.","year":"1987","unstructured":"P. Mani-Levitska and J. Pach . Decomposition problems for multiple coverings with unit balls . Manuscript , 1987 . P. Mani-Levitska and J. Pach. Decomposition problems for multiple coverings with unit balls. Manuscript, 1987."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.197205"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276866"},{"key":"e_1_3_2_1_34_1","volume-title":"Derandomizing the Lov\u00e1sz local lemma more effectively. Arxiv preprint arXiv:0807.2120","author":"Moser R.A.","year":"2008","unstructured":"R.A. Moser . Derandomizing the Lov\u00e1sz local lemma more effectively. Arxiv preprint arXiv:0807.2120 , 2008 . R.A. Moser. Derandomizing the Lov\u00e1sz local lemma more effectively. Arxiv preprint arXiv:0807.2120, 2008."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536462"},{"key":"e_1_3_2_1_36_1","volume-title":"A constructive proof of the general Lovasz Local Lemma. Arxiv preprint arXiv:0903.0544","author":"Moser R.A.","year":"2009","unstructured":"R.A. Moser and G. Tardos . A constructive proof of the general Lovasz Local Lemma. Arxiv preprint arXiv:0903.0544 , 2009 . R.A. Moser and G. Tardos. A constructive proof of the general Lovasz Local Lemma. Arxiv preprint arXiv:0903.0544, 2009."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90044-9"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347150"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1073287"}],"event":{"name":"STOC'10: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Cambridge Massachusetts USA","acronym":"STOC'10"},"container-title":["Proceedings of the forty-second ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806712","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806689.1806712","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:36Z","timestamp":1750246776000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806712"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,5]]},"references-count":39,"alternative-id":["10.1145\/1806689.1806712","10.1145\/1806689"],"URL":"https:\/\/doi.org\/10.1145\/1806689.1806712","relation":{},"subject":[],"published":{"date-parts":[[2010,6,5]]},"assertion":[{"value":"2010-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}