{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:51Z","timestamp":1750219851367,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,17]],"date-time":"2023-06-17T00:00:00Z","timestamp":1686960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-2045354"],"award-info":[{"award-number":["CCF-2045354"]}]},{"name":"Sloan","award":["Research Fellowship"],"award-info":[{"award-number":["Research Fellowship"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,17]]},"DOI":"10.1145\/3558481.3591104","type":"proceedings-article","created":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T22:22:03Z","timestamp":1685571723000},"page":"367-377","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Quadratic Speedups in Parallel Sampling from Determinantal Distributions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4394-3530","authenticated-orcid":false,"given":"Nima","family":"Anari","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-3669-037X","authenticated-orcid":false,"given":"Callum","family":"Burgess","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0109-9201","authenticated-orcid":false,"given":"Kevin","family":"Tian","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0271-9687","authenticated-orcid":false,"given":"Thuy-Duong","family":"Vuong","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,17]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_3_1_1","DOI":"10.1137\/0403039"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_2_1","DOI":"10.1145\/3357713.3384317"},{"doi-asserted-by":"crossref","unstructured":"Yeganeh Alimohammadi Nima Anari Kirankumar Shiragur and Thuy-Duong Vuong. 2021. Fractionally log-concave and sector-stable polynomials: counting planar matchings and more. arXiv preprint arXiv:2102.02708.","key":"e_1_3_2_3_3_1","DOI":"10.1145\/3406325.3451123"},{"unstructured":"Nima Anari Michal Derezinski Thuy-Duong Vuong and Elizabeth Yang. 2021. Domain sparsification of discrete distributions using entropic independence. CoRR abs\/2109.06442.","key":"e_1_3_2_3_4_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_5_1","DOI":"10.1109\/FOCS46700.2020.00126"},{"unstructured":"Nima Anari Nathan Hu Amin Saberi and Aaron Schild. 2020. Sampling arborescences in parallel. arXiv preprint arXiv:2012.09502.","key":"e_1_3_2_3_6_1"},{"doi-asserted-by":"crossref","unstructured":"Nima Anari Yizhi Huang Thuy-Duong Vuong Brian Xu and Katherine Yu. Parallel discrete sampling via continuous walks. (2023).","key":"e_1_3_2_3_7_1","DOI":"10.1145\/3564246.3585207"},{"key":"e_1_3_2_3_8_1","volume-title":"Huy Tuan Pham, and Thuy-Duong Vuong","author":"Anari Nima","year":"2021","unstructured":"Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. 2021. Entropic independence i: modified log-sobolev inequalities for fractionally log-concave distributions and high-temperature ising models. CoRR, abs\/2106.04105. arXiv: 2106.04105."},{"key":"e_1_3_2_3_9_1","volume-title":"Huy Tuan Pham, and Thuy-Duong Vuong","author":"Anari Nima","year":"2021","unstructured":"Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. 2021. Entropic independence ii: optimal sampling and concentration via restricted modified log-sobolev inequalities. arXiv preprint arXiv:2111.03247."},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_10_1","DOI":"10.1109\/FOCS46700.2020.00125"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_11_1","DOI":"10.1145\/3313276.3316385"},{"unstructured":"Alexander Barvinok. 2018. Approximating real-rooted and stable polynomials with combinatorial applications. arXiv preprint arXiv:1806.07404.","key":"e_1_3_2_3_12_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_13_1","DOI":"10.1090\/S0894-0347-08-00618-8"},{"volume-title":"FOCS.","author":"Broder Andrei Z","unstructured":"Andrei Z Broder. 1989. Generating random spanning trees. In FOCS. Vol. 89. Citeseer, 442--447.","key":"e_1_3_2_3_14_1"},{"volume-title":"Advances in Neural Information Processing Systems","author":"Brunel Victor-Emmanuel","unstructured":"Victor-Emmanuel Brunel. 2018. Learning signed determinantal point processes through the principal minor assignment problem. In Advances in Neural Information Processing Systems. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, (Eds.) Vol. 31. Curran Associates, Inc., 7365--7374.","key":"e_1_3_2_3_15_1"},{"unstructured":"L Elisa Celis Amit Deshpande Tarun Kathuria Damian Straszak and Nisheeth K Vishnoi. 2016. On the complexity of constrained determinantal point processes. arXiv preprint arXiv:1608.00554.","key":"e_1_3_2_3_16_1"},{"unstructured":"Zongchen Chen Kuikui Liu and Eric Vigoda. 2021. Spectral independence via stability and applications to holant-type problems. arXiv preprint arXiv:2106.03366.","key":"e_1_3_2_3_17_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_18_1","DOI":"10.1109\/SFCS.1975.14"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_19_1","DOI":"10.1090\/noti2202"},{"key":"e_1_3_2_3_20_1","volume-title":"International Conference on Machine Learning. PMLR, 1774--1783","author":"Elfeki Mohamed","year":"2019","unstructured":"Mohamed Elfeki, Camille Couprie, Morgane Riviere, and Mohamed Elhoseiny. 2019. Gdpp: learning diverse generations using determinantal point processes. In International Conference on Machine Learning. PMLR, 1774--1783."},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_21_1","DOI":"10.1137\/1.9781611976465.127"},{"unstructured":"Mike Gartrell Victor-Emmanuel Brunel Elvis Dohmatob and Syrine Krichene. 2019. Learning nonsymmetric determinantal point processes. ArXiv abs\/1905.12962.","key":"e_1_3_2_3_22_1"},{"key":"e_1_3_2_3_23_1","volume-title":"Scalable learning and map inference for nonsymmetric determinantal point processes. (2020). arXiv","author":"Gartrell Mike","year":"2006","unstructured":"Mike Gartrell, Insu Han, Elvis Dohmatob, Jennifer Gillenwater, and Victor-Emmanuel Brunel. 2020. Scalable learning and map inference for nonsymmetric determinantal point processes. (2020). arXiv: 2006.09862 [cs.LG]."},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_24_1","DOI":"10.1145\/2959"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_25_1","DOI":"10.1109\/SFCS.1987.3"},{"unstructured":"Boqing Gong Wei-lun Chao Kristen Grauman and Fei Sha. 2014. Large-margin determinantal point processes. (2014). arXiv: 1411.1537 [stat.ML].","key":"e_1_3_2_3_26_1"},{"doi-asserted-by":"crossref","unstructured":"Mark R Jerrum Leslie G Valiant and Vijay V Vazirani. 1986. Random generation of combinatorial structures from a uniform distribution. Theoretical computer science 43 169--188.","key":"e_1_3_2_3_27_1","DOI":"10.1016\/0304-3975(86)90174-X"},{"unstructured":"Pieter Kasteleyn. 1967. Graph theory and crystal physics. Graph theory and theoretical physics 43--110.","key":"e_1_3_2_3_28_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_29_1","DOI":"10.1561\/2200000044"},{"unstructured":"Alex Kulesza and Ben Taskar. 2012. K-dpps: fixed-size determinantal point processes. (2012).","key":"e_1_3_2_3_30_1"},{"unstructured":"Chengtao Li Stefanie Jegelka and Suvrit Sra. 2016. Fast DPP sampling for nystr\u00f6m with application to kernel methods. CoRR abs\/1603.06052. arXiv: 1603.06052.","key":"e_1_3_2_3_31_1"},{"key":"e_1_3_2_3_32_1","volume-title":"Uncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012, (Oct.","author":"Lin Hui","year":"2012","unstructured":"Hui Lin and Jeff Bilmes. 2012. Learning mixtures of submodular shells with application to document summarization. Uncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012, (Oct. 2012)."},{"unstructured":"Hongyang Liu and Yitong Yin. 2021. Simple parallel algorithms for single-site dynamics. arXiv preprint arXiv:2111.04044.","key":"e_1_3_2_3_33_1"},{"unstructured":"Zelda Mariet and Suvrit Sra. 2015. Fixed-point algorithms for determinantal point processes. CoRR abs\/1508.00792.","key":"e_1_3_2_3_34_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_35_1","DOI":"10.1137\/16M1101003"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_36_1","DOI":"10.1016\/0304-3975(94)00289-U"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_37_1","DOI":"10.1145\/3269206.3272018"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"acronym":"SPAA '23","name":"SPAA '23: 35th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Orlando FL USA"},"container-title":["Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558481.3591104","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558481.3591104","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558481.3591104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:06Z","timestamp":1750178826000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558481.3591104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,17]]},"references-count":37,"alternative-id":["10.1145\/3558481.3591104","10.1145\/3558481"],"URL":"https:\/\/doi.org\/10.1145\/3558481.3591104","relation":{},"subject":[],"published":{"date-parts":[[2023,6,17]]},"assertion":[{"value":"2023-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}