{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T13:08:45Z","timestamp":1783170525591,"version":"3.54.6"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T00:00:00Z","timestamp":1349049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","award":["15848"],"award-info":[{"award-number":["15848"]}],"id":[{"id":"10.13039\/501100004965","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0435060, CCR-0325197, EN-CS-0329609"],"award-info":[{"award-number":["CNS-0435060, CCR-0325197, EN-CS-0329609"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-0435060, CCR-0325197, EN-CS-0329609"],"award-info":[{"award-number":["CNS-0435060, CCR-0325197, EN-CS-0329609"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["2009\/0216\/1DP\/1.1.1.2.0\/09\/APIA\/VIAA\/044"],"award-info":[{"award-number":["2009\/0216\/1DP\/1.1.1.2.0\/09\/APIA\/VIAA\/044"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["PIRG02-GA-2007-224886"],"award-info":[{"award-number":["PIRG02-GA-2007-224886"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-08-EMER-012(ORAC project)"],"award-info":[{"award-number":["ANR-08-EMER-012(ORAC project)"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p>The Lov\u00e1sz Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of \u201cweakly dependent\u201d criteria. We show that the LLL extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions.<\/jats:p>\n          <jats:p>\n            Our result immediately applies to the\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:sc>qsat<\/jats:sc>\n            problem (quantum analog of\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:sc>sat<\/jats:sc>\n            ): For instance we show that any collection of rank-1 projectors, with the property that each qubit appears in at most 2\n            <jats:italic>\n              <jats:sup>k<\/jats:sup>\n            <\/jats:italic>\n            \/(\n            <jats:italic>e<\/jats:italic>\n            \u010b\n            <jats:italic>k<\/jats:italic>\n            ) of them, has a joint satisfiable state.\n          <\/jats:p>\n          <jats:p>\n            We then apply our results to the recently studied model of random\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:sc>qsat<\/jats:sc>\n            . Recent works have shown that the satisfiable region extends up to a density of 1 in the large\n            <jats:italic>k<\/jats:italic>\n            limit, where the density is the ratio of projectors to qubits. Using a hybrid approach building on work by Laumann et al. [2009, 2010] we greatly extend the known satisfiable region for random\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:sc>qsat<\/jats:sc>\n            to a density of \u03a9(2\n            <jats:italic>\n              <jats:sup>k<\/jats:sup>\n            <\/jats:italic>\n            \/\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ). Since our tool allows us to show the existence of joint satisfying states without the need to construct them, we are able to penetrate into regions where the satisfying states are conjectured to be entangled, avoiding the need to construct them, which has limited previous approaches to product states.\n          <\/jats:p>","DOI":"10.1145\/2371656.2371659","type":"journal-article","created":{"date-parts":[[2012,11,13]],"date-time":"2012-11-13T15:03:58Z","timestamp":1352819038000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["A quantum Lov\u00e1sz local lemma"],"prefix":"10.1145","volume":"59","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[{"name":"University of Latvia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Julia","family":"Kempe","sequence":"additional","affiliation":[{"name":"Universite de Paris 7 and Tel Aviv University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Or","family":"Sattath","sequence":"additional","affiliation":[{"name":"The Hebrew University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,11,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2021256.2021261"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.997.abs"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-04-00464-3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"e_1_2_1_5_1","unstructured":"Alon N. and Spencer J. H. 1993. A note on coloring random k-sets. http:\/\/www.cs.tau.ac.il\/~nogaa\/PDFS\/kset2.pdf.  Alon N. and Spencer J. H. 1993. A note on coloring random k-sets. http:\/\/www.cs.tau.ac.il\/~nogaa\/PDFS\/kset2.pdf."},{"key":"e_1_2_1_6_1","unstructured":"Alon N. and Spencer J. H. 2004. The Probabilistic Method. Wiley-Interscience.  Alon N. and Spencer J. H. 2004. The Probabilistic Method. Wiley-Interscience."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806712"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1178243286"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"e_1_2_1_10_1","unstructured":"Beigi S. and Shor P. W. 2007. On the complexity of computing zero-error and Holevo capacity of quantum channels. Arxiv preprint arXiv:0709.2090.  Beigi S. and Shor P. W. 2007. On the complexity of computing zero-error and Holevo capacity of quantum channels. Arxiv preprint arXiv:0709.2090."},{"key":"e_1_2_1_11_1","volume-title":"Random Graphs","author":"Bollob\u00e1s B.","unstructured":"Bollob\u00e1s , B. 2001. Random Graphs 2 nd Ed. Cambridge University Press . Bollob\u00e1s, B. 2001. Random Graphs 2nd Ed. Cambridge University Press.","edition":"2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1006"},{"key":"e_1_2_1_13_1","unstructured":"Bravyi S. 2006. Efficient algorithm for a quantum analogue of 2-SAT. Arxiv preprint quant-ph\/0602108.  Bravyi S. 2006. Efficient algorithm for a quantum analogue of 2-SAT. Arxiv preprint quant-ph\/0602108."},{"key":"e_1_2_1_14_1","unstructured":"Bravyi S. Moore C. and Russell A. 2010. Bounds on the quantum satisfibility threshold. InInnovations in Computer Science 482--489.  Bravyi S. Moore C. and Russell A. 2010. Bounds on the quantum satisfibility threshold. InInnovations in Computer Science 482--489."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/08072689X"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267789"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 11th Symposium on Discrete Algorithms. 30--39","author":"Czumaj A.","unstructured":"Czumaj , A. and Scheideler , C . 2000. Coloring non-uniform hypergraphs: A new algorithmic approach to the general Lov\u00e1sz local lemma . In Proceedings of the 11th Symposium on Discrete Algorithms. 30--39 . Czumaj, A. and Scheideler, C. 2000. Coloring non-uniform hypergraphs: A new algorithmic approach to the general Lov\u00e1sz local lemma. In Proceedings of the 11th Symposium on Discrete Algorithms. 30--39."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. 163--174","author":"Diaz J.","unstructured":"Diaz , J. , Kirousis , L. , Mitsche , D. , and Perez-Gimenez , X . 2008. A new upper bound for 3-sat . In Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. 163--174 . Diaz, J., Kirousis, L., Mitsche, D., and Perez-Gimenez, X. 2008. A new upper bound for 3-sat. In Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. 163--174."},{"key":"e_1_2_1_19_1","volume-title":"Graph Theory (Graduate Texts in Mathematics)","author":"Diestel R.","unstructured":"Diestel , R. 1997. Graph Theory (Graduate Texts in Mathematics) . Springer . Diestel, R. 1997. Graph Theory (Graduate Texts in Mathematics). Springer."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_72"},{"key":"e_1_2_1_21_1","first-page":"609","article-title":"Problems and results on 3-chromatic hypergraphs and some related questions","volume":"2","author":"Erdos P.","year":"1975","unstructured":"Erdos , P. and Lov\u00e1sz , L. 1975 . Problems and results on 3-chromatic hypergraphs and some related questions . Infinite Finite Sets 2 , 609 -- 627 . Erdos, P. and Lov\u00e1sz, L. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. Infinite Finite Sets 2, 609--627.","journal-title":"Infinite Finite Sets"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"e_1_2_1_23_1","unstructured":"Fortnow L. 2009. A kolmogorov complexity proof of the lov\u00e1sz local lemma. http:\/\/blog.computationa lcomplexity.org\/2009\/06\/kolmogorov-complexity-proof-of-lov.html.  Fortnow L. 2009. A kolmogorov complexity proof of the lov\u00e1sz local lemma. http:\/\/blog.computationa lcomplexity.org\/2009\/06\/kolmogorov-complexity-proof-of-lov.html."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03456-5_3"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. 664--674","author":"Gebauer H.","unstructured":"Gebauer , H. , Szab\u00f3 , T. , and Tardos , G . 2011. The local lemma is tight for SAT . In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. 664--674 . Gebauer, H., Szab\u00f3, T., and Tardos, G. 2011. The local lemma is tight for SAT. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. 664--674."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Goerdt A. 1992. A threshold for unsatisfiability. In Mathematical Foundations of Computer Science. 264--274.   Goerdt A. 1992. A threshold for unsatisfiability. In Mathematical Foundations of Computer Science. 264--274.","DOI":"10.1007\/3-540-55808-X_25"},{"key":"e_1_2_1_28_1","unstructured":"Hajiaghayi M. T. and Sorkin G. B. 2003. The satisfiability threshold of random 3-SAT is at least 3.52. Arxiv preprint math\/0310193.  Hajiaghayi M. T. and Sorkin G. B. 2003. The satisfiability threshold of random 3-SAT is at least 3.52. Arxiv preprint math\/0310193."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(04)00462-7"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Kirkpatrick S. and Selman B. 1994. Critical behavior in the satisfiability of random boolean expressions. Sci. 264 5163 1297--1301.  Kirkpatrick S. and Selman B. 1994. Critical behavior in the satisfiability of random boolean expressions. Sci. 264 5163 1297--1301.","DOI":"10.1126\/science.264.5163.1297"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993669"},{"key":"e_1_2_1_34_1","volume-title":"Linear Algebra and Geometry","author":"Kostrikin A. I.","unstructured":"Kostrikin , A. I. 1997. Linear Algebra and Geometry . Taylor & Francis . Kostrikin, A. I. 1997. Linear Algebra and Geometry. Taylor & Francis."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.81.062345"},{"key":"e_1_2_1_36_1","unstructured":"Laumann C. R. Moessner R. Scardicchio A. and Sondhi S. L. 2009. Phase transitions and random quantum satisfiability. Arxiv preprint arXiv:0903.1904.  Laumann C. R. Moessner R. Scardicchio A. and Sondhi S. L. 2009. Phase transitions and random quantum satisfiability. Arxiv preprint arXiv:0903.1904."},{"key":"e_1_2_1_37_1","unstructured":"Mani-Levitska P. and Pach J. 1987. Decomposition problems for multiple coverings with unit balls. http:\/\/infoscience.epfl.ch\/record\/130089\/files\/unsplittable.pdf.  Mani-Levitska P. and Pach J. 1987. Decomposition problems for multiple coverings with unit balls. http:\/\/infoscience.epfl.ch\/record\/130089\/files\/unsplittable.pdf."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.197205"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Mezard M. Parisi G. and Zecchina R. 2002. Analytic and algorithmic solution of random satisfiability problems. Sci. 297 5582 812--815.  Mezard M. Parisi G. and Zecchina R. 2002. Analytic and algorithmic solution of random satisfiability problems. Sci. 297 5582 812--815.","DOI":"10.1126\/science.1073287"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022886412117"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M. and Upfal E. 2005. Probability and Computing - Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.   Mitzenmacher M. and Upfal E. 2005. Probability and Computing - Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276866"},{"key":"e_1_2_1_43_1","unstructured":"Moser R. A. 2008. Derandomizing the Lov\u00e1sz local lemma more effectively. Arxiv preprint arXiv:0807.2120.  Moser R. A. 2008. Derandomizing the Lov\u00e1sz local lemma more effectively. Arxiv preprint arXiv:0807.2120."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536462"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579368"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90044-9"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 19th Symposium on Discrete Algorithms. 611--620","author":"Srinivasan A.","year":"2008","unstructured":"Srinivasan , A. 2008 . Improved algorithmic versions of the Lov\u00e1sz local lemma . In Proceedings of the 19th Symposium on Discrete Algorithms. 611--620 . Srinivasan, A. 2008. Improved algorithmic versions of the Lov\u00e1sz local lemma. In Proceedings of the 19th Symposium on Discrete Algorithms. 611--620."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2371656.2371659","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2371656.2371659","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:21:18Z","timestamp":1750238478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2371656.2371659"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":48,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1145\/2371656.2371659"],"URL":"https:\/\/doi.org\/10.1145\/2371656.2371659","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10]]},"assertion":[{"value":"2010-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}