{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T11:47:03Z","timestamp":1767008823540,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":73,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"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":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451123","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"433-446","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Fractionally log-concave and sector-stable polynomials: counting planar matchings and more"],"prefix":"10.1145","author":[{"given":"Yeganeh","family":"Alimohammadi","sequence":"first","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Nima","family":"Anari","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Kirankumar","family":"Shiragur","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0271-9687","authenticated-orcid":false,"given":"Thuy-Duong","family":"Vuong","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Raja Hafiz Affandi Emily B. Fox Ryan P. Adams and Ben Taskar. 2014. Learning the Parameters of Determinantal Point Process Kernels."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384317"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00125"},{"key":"e_1_3_2_1_4_1","volume-title":"Shayan Oveis Gharan, and Cynthia Vinzant","author":"Anari Nima","year":"2018","unstructured":"Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. 2018. Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids. CoRR, abs\/1811.01600, 2018."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316385"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055469"},{"key":"e_1_3_2_1_7_1","first-page":"115","volume-title":"Proceedings of the 29th Conference on Learning Theory. JMLR Workshop and Conference Proceedings. 49","author":"Anari Nima","year":"2016","unstructured":"Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei. 2016. Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes. In Proceedings of the 29th Conference on Learning Theory. JMLR Workshop and Conference Proceedings. 49, PMLR. Pages 103\u2013115."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/focs.2018.00013"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250809"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-009-0189-3"},{"key":"e_1_3_2_1_11_1","first-page":"2","article-title":"Negative dependence and the geometry of polynomials","volume":"22","author":"Borcea Julius","year":"2009","unstructured":"Julius Borcea, Petter Br\u00e4nd\u00e9n, and Thomas Liggett. 2009. Negative dependence and the geometry of polynomials. Journal of the American Mathematical Society, 22, 2, 2009. Pages 521\u2013567.","journal-title":"Journal of the American Mathematical Society"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Alexei Borodin. 2009. Determinantal point processes.","DOI":"10.1214\/07-AIHP115"},{"key":"e_1_3_2_1_13_1","volume-title":"Izrail Moiseevich Gel'fand, and Neil White","author":"Borovik Alexandre V","year":"2003","unstructured":"Alexandre V Borovik, Izrail Moiseevich Gel'fand, and Neil White. 2003. Coxeter matroids. In Coxeter Matroids. Springer. Pages 151\u2013197."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2007.05.011"},{"key":"e_1_3_2_1_15_1","volume-title":"Lorentzian polynomials. arXiv preprint arXiv:1902.03719","author":"Br\u00e4nd\u00e9n Petter","year":"2019","unstructured":"Petter Br\u00e4nd\u00e9n and June Huh. 2019. Lorentzian polynomials. arXiv preprint arXiv:1902.03719, 2019."},{"key":"e_1_3_2_1_16_1","first-page":"7365","article-title":"Learning Signed Determinantal Point Processes through the Principal Minor Assignment Problem","author":"Brunel Victor-Emmanuel","year":"2018","unstructured":"Victor-Emmanuel Brunel, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett. 2018. Learning Signed Determinantal Point Processes through the Principal Minor Assignment Problem. In Advances in Neural Information Processing Systems. 31, Curran Associates, Inc.. Pages 7365\u20137374. https:\/\/proceedings.neurips.cc\/paper\/2018\/file\/e1228be46de6a0234ac22ded31417bc7-Paper.pdf","journal-title":"Advances in Neural Information Processing Systems. 31, Curran Associates, Inc.. Pages"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989121"},{"key":"e_1_3_2_1_18_1","volume-title":"On the complexity of constrained determinantal point processes. arXiv preprint arXiv:1608.00554","author":"Celis L Elisa","year":"2016","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, 2016."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3020847.3020868"},{"key":"e_1_3_2_1_20_1","volume-title":"Rapid mixing for colorings via spectral independence. arXiv preprint arXiv:2007.08058","author":"Chen Zongchen","year":"2020","unstructured":"Zongchen Chen, Andreas Galanis, Daniel \\v Stefankovi\u010d, and Eric Vigoda. 2020. Rapid mixing for colorings via spectral independence. arXiv preprint arXiv:2007.08058, 2020."},{"key":"e_1_3_2_1_21_1","volume-title":"Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion. arXiv preprint arXiv:2011.02075","author":"Chen Zongchen","year":"2020","unstructured":"Zongchen Chen, Kuikui Liu, and Eric Vigoda. 2020. Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion. arXiv preprint arXiv:2011.02075, 2020."},{"key":"e_1_3_2_1_22_1","volume-title":"Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. arXiv preprint arXiv:2004.09083","author":"Chen Zongchen","year":"2020","unstructured":"Zongchen Chen, Kuikui Liu, and Eric Vigoda. 2020. Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. arXiv preprint arXiv:2004.09083, 2020."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8121"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.94"},{"key":"e_1_3_2_1_25_1","volume-title":"trees, and flowers. Canadian Journal of mathematics, 17","author":"Edmonds Jack","year":"1965","unstructured":"Jack Edmonds. 1965. Paths, trees, and flowers. Canadian Journal of mathematics, 17, 1965. Pages 449\u2013467."},{"key":"e_1_3_2_1_26_1","volume-title":"Log concavity and concentration of Lipschitz functions on the Boolean hypercube. arXiv preprint arXiv:2007.13108","author":"Eldan Ronen","year":"2020","unstructured":"Ronen Eldan and Omer Shamir. 2020. Log concavity and concentration of Lipschitz functions on the Boolean hypercube. arXiv preprint arXiv:2007.13108, 2020."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323206"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129716"},{"key":"e_1_3_2_1_29_1","volume-title":"Rapid mixing from spectral independence beyond the Boolean domain. arXiv preprint arXiv:2007.08091","author":"Feng Weiming","year":"2020","unstructured":"Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang. 2020. Rapid mixing from spectral independence beyond the Boolean domain. arXiv preprint arXiv:2007.08091, 2020."},{"key":"e_1_3_2_1_30_1","first-page":"2019","article-title":"Bipartite perfect matching is in quasi-NC","volume":"0","author":"Fenner Stephen","year":"2019","unstructured":"Stephen Fenner, Rohit Gurjar, and Thomas Thierauf. 2019. Bipartite perfect matching is in quasi-NC. SIAM J. Comput., 0, 2019. Pages STOC16\u2013218.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_31_1","volume-title":"On the theory of Pfaffian orientations. I. Perfect matchings and permanents. the electronic journal of combinatorics","author":"Galluccio Anna","year":"1999","unstructured":"Anna Galluccio and Martin Loebl. 1999. On the theory of Pfaffian orientations. I. Perfect matchings and permanents. the electronic journal of combinatorics, 1999. Pages R6\u2013R6."},{"key":"e_1_3_2_1_32_1","first-page":"965","volume-title":"Journal of Mathematics and Mechanics","author":"Lars","year":"1959","unstructured":"Lars G\\r arding. 1959. An inequality for hyperbolic polynomials. Journal of Mathematics and Mechanics, 1959. Pages 957\u2013965."},{"key":"e_1_3_2_1_33_1","volume-title":"Learning Nonsymmetric Determinantal Point Processes. ArXiv, abs\/1905.12962","author":"Gartrell Mike","year":"2019","unstructured":"Mike Gartrell, Victor-Emmanuel Brunel, Elvis Dohmatob, and Syrine Krichene. 2019. Learning Nonsymmetric Determinantal Point Processes. ArXiv, abs\/1905.12962, 2019."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2959100.2959178"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.2.350"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01877590"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1214\/154957806000000078"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01010403"},{"key":"e_1_3_2_1_39_1","series-title":"SIAM journal on computing, 18, 6","volume-title":"Approximating the permanent","author":"Jerrum Mark","year":"1989","unstructured":"Mark Jerrum and Alistair Sinclair. 1989. Approximating the permanent. SIAM journal on computing, 18, 6, 1989. Pages 1149\u20131178."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"e_1_3_2_1_41_1","volume-title":"Random generation of combinatorial structures from a uniform distribution. Theoretical computer science, 43","author":"Jerrum Mark R","year":"1986","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, 1986. Pages 169\u2013188."},{"key":"e_1_3_2_1_42_1","first-page":"1","article-title":"Random matrices and determinantal processes","author":"Johansson Kurt","year":"2005","unstructured":"Kurt Johansson. 2005. Random matrices and determinantal processes. In Mathematical Statistical Physics, Session LXXXIII: Lecture Notes of the Les Houches Summer School. Pages 1\u201356.","journal-title":"Mathematical Statistical Physics, Session LXXXIII: Lecture Notes of the Les Houches Summer School. Pages"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579407"},{"key":"e_1_3_2_1_44_1","volume-title":"Graph theory and crystal physics. Graph theory and theoretical physics","author":"Kasteleyn Pieter","year":"1967","unstructured":"Pieter Kasteleyn. 1967. Graph theory and crystal physics. Graph theory and theoretical physics, 1967. Pages 43\u2013110."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-8914(61)90063-5"},{"key":"e_1_3_2_1_46_1","volume-title":"On sampling and greedy map inference of constrained determinantal point processes. arXiv preprint arXiv:1607.01551","author":"Kathuria Tarun","year":"2016","unstructured":"Tarun Kathuria and Amit Deshpande. 2016. On sampling and greedy map inference of constrained determinantal point processes. arXiv preprint arXiv:1607.01551, 2016."},{"key":"e_1_3_2_1_47_1","volume-title":"High dimensional random walks and colorful expansion. arXiv preprint arXiv:1604.02947","author":"Kaufman Tali","year":"2016","unstructured":"Tali Kaufman and David Mass. 2016. High dimensional random walks and colorful expansion. arXiv preprint arXiv:1604.02947, 2016."},{"key":"e_1_3_2_1_48_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM","author":"Kaufman Tali","year":"2018","unstructured":"Tali Kaufman and Izhar Oppenheim. 2018. High order random walks: Beyond spectral gap. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2018)."},{"volume-title":"Theory of computation","author":"Kozen Dexter C","key":"e_1_3_2_1_49_1","unstructured":"Dexter C Kozen. 2006. Theory of computation. Springer Science & Business Media."},{"key":"e_1_3_2_1_50_1","first-page":"2008","article-title":"Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies","volume":"9","author":"Krause Andreas","year":"2008","unstructured":"Andreas Krause, Ajit Singh, and Carlos Guestrin. 2008. Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies. J. Mach. Learn. Res., 9, June, 2008. Pages 235\u2013284. issn:1532-4435","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_51_1","volume-title":"Proceedings of the 28th International Conference on International Conference on Machine Learning. ICML'11. Omnipress. Pages 1193\u20131200","author":"Kulesza Alex","year":"2011","unstructured":"Alex Kulesza and Ben Taskar. 2011. K-DPPs: Fixed-Size Determinantal Point Processes. In Proceedings of the 28th International Conference on International Conference on Machine Learning. ICML'11. Omnipress. Pages 1193\u20131200. isbn:9781450306195"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000044"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1111\/rssb.12096"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"crossref","unstructured":"David A Levin and Yuval Peres. 2017. Markov chains and mixing times. 107 American Mathematical Soc..","DOI":"10.1090\/mbk\/107"},{"key":"e_1_3_2_1_55_1","volume-title":"Proceedings of the 33rd International Conference on International Conference on Machine Learning -","volume":"48","author":"Li Chengtao","year":"2016","unstructured":"Chengtao Li, Stefanie Jegelka, and Suvrit Sra. 2016. Fast DPP Sampling for Nystr\u00f6m with Application to Kernel Methods. In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48. ICML'16. JMLR.org. Pages 2061\u20132070."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/3020652.3020704"},{"key":"e_1_3_2_1_57_1","first-page":"574","volume-title":"FCT 1979, Proceedings of the Conference on Algebraic, Arthmetic, and Categorial Methods in Computation Theory, Berlin\/Wendisch-Rietz","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1979","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Lothar Budach. 1979. On determinants, matchings, and random algorithms. In Fundamentals of Computation Theory, FCT 1979, Proceedings of the Conference on Algebraic, Arthmetic, and Categorial Methods in Computation Theory, Berlin\/Wendisch-Rietz, Germany, September 17-21, 1979. Akademie-Verlag, Berlin. Pages 565\u2013574."},{"key":"e_1_3_2_1_58_1","volume-title":"Random walks on Ramanujan complexes and digraphs. arXiv preprint arXiv:1702.05452","author":"Lubetzky Eyal","year":"2017","unstructured":"Eyal Lubetzky, Alex Lubotzky, and Ori Parzanchevski. 2017. Random walks on Ramanujan complexes and digraphs. arXiv preprint arXiv:1702.05452, 2017."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.2307\/1425855"},{"key":"e_1_3_2_1_60_1","volume-title":"Central limit theorems and the geometry of polynomials. arXiv preprint arXiv:1908.09020","author":"Michelen Marcus","year":"2019","unstructured":"Marcus Michelen and Julian Sahasrabudhe. 2019. Central limit theorems and the geometry of polynomials. arXiv preprint arXiv:1908.09020, 2019."},{"key":"e_1_3_2_1_61_1","series-title":"Series B, to appear","volume-title":"On the expansion of 0-1 polytopes. Journal of Combinatorial Theory","author":"Mihail Milena","year":"1989","unstructured":"Milena Mihail and Umesh Vazirani. 1989. On the expansion of 0-1 polytopes. Journal of Combinatorial Theory, Series B, to appear, 1989."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.383347"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9948-x"},{"key":"e_1_3_2_1_64_1","first-page":"1500","volume-title":"Fast Mixing for Discrete Point Processes. Proceedings of Machine Learning Research. 40","author":"Rebeschini Patrick","year":"2015","unstructured":"Patrick Rebeschini, Amin Karbasi, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale. 2015. Fast Mixing for Discrete Point Processes. Proceedings of Machine Learning Research. 40, PMLR. Pages 1480\u20131500. http:\/\/proceedings.mlr.press\/v40\/Rebeschini15.html"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop"},{"key":"e_1_3_2_1_67_1","volume-title":"Latin American Symposium on Theoretical Informatics. Pages 873\u2013885","author":"Stefankovi\u010d Daniel","year":"2018","unstructured":"Daniel \\v Stefankovi\u010d, Eric Vigoda, and John Wilmes. 2018. On counting perfect matchings in general graphs. In Latin American Symposium on Theoretical Informatics. Pages 873\u2013885."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(90)90070-4"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055457"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1080\/14786436108243366"},{"key":"e_1_3_2_1_71_1","volume-title":"The complexity of computing the permanent. Theoretical computer science, 8, 2","author":"Valiant Leslie G","year":"1979","unstructured":"Leslie G Valiant. 1979. The complexity of computing the permanent. Theoretical computer science, 8, 2, 1979. Pages 189\u2013201."},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.07.007"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.87.404"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451123","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":73,"alternative-id":["10.1145\/3406325.3451123","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451123","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}