{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:10Z","timestamp":1781077990281,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":20,"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"}],"funder":[{"name":"ERC","award":["740282"],"award-info":[{"award-number":["740282"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451002","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1118-1131","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Bipartite perfect matching as a real polynomial"],"prefix":"10.1145","author":[{"given":"Gal","family":"Beniamini","sequence":"first","affiliation":[{"name":"Hebrew University of Jerusalem, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noam","family":"Nisan","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Gal Beniamini. 2020. The Dual Polynomial of Bipartite Perfect Matching. arxiv:2004.14318 [cs.DM]"},{"key":"e_1_3_2_1_2_1","volume-title":"Formal power series and algebraic combinatorics","author":"Billera Louis J","unstructured":"Louis J Billera and Aravamuthan Sarangarajan. 1994. The Combinatorics of Permutation Polytopes.. In Formal power series and algebraic combinatorics, Vol. 24. 1\u201323."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.02.010"},{"key":"e_1_3_2_1_4_1","first-page":"455","article-title":"On random matrices. Magyar Tud. Akad. Mat","volume":"8","author":"Erd\u0151s Paul","year":"1964","unstructured":"Paul Erd\u0151s and Alfred R\u00e9nyi. 1964. On random matrices. Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl 8, 455-461 (1964), 1964.","journal-title":"Kutat\u00f3 Int. K\u00f6zl"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80046-9"},{"key":"e_1_3_2_1_6_1","volume-title":"Convex polytopes","author":"Gr\u00fcnbaum Branko","unstructured":"Branko Gr\u00fcnbaum. 2013. Convex polytopes. Vol. 221. Springer Science & Business Media."},{"key":"e_1_3_2_1_7_1","first-page":"351","article-title":"Rectangular configurations which can be covered by 2$\\times$1 rectangles","volume":"8","author":"Hetyei G\u00e1bor","year":"1964","unstructured":"G\u00e1bor Hetyei. 1964. Rectangular configurations which can be covered by 2$\\times$1 rectangles. P\u00e9csi Tan. Foisk. K\u00f6zl 8 (1964), 351\u2013367.","journal-title":"P\u00e9csi Tan. Foisk. K\u00f6zl"},{"key":"e_1_3_2_1_8_1","volume-title":"New bounds on the classical and quantum communication complexity of some graph properties. arXiv preprint arXiv:1204.4596","author":"Ivanyos G\u00e1bor","year":"2012","unstructured":"G\u00e1bor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, and Ronald de Wolf. 2012. New bounds on the classical and quantum communication complexity of some graph properties. arXiv preprint arXiv:1204.4596 (2012)."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579140"},{"key":"e_1_3_2_1_10_1","volume-title":"Combinatorics and number theory of counting sequences","author":"Mezo Istvan","unstructured":"Istvan Mezo. 2019. Combinatorics and number theory of counting sequences. Chapman and Hall\/CRC."},{"key":"e_1_3_2_1_11_1","volume-title":"STACS","author":"Mukhopadhyay Sagnik","year":"2019","unstructured":"Sagnik Mukhopadhyay and Bruno Loff. 2019. Lifting Theorems for Equality.. In STACS 2019."},{"key":"e_1_3_2_1_12_1","unstructured":"Ilan Newman Michael Saks and Mario Szegedy. 2008. Decision Trees - Unpublished Manuscript. (2008)."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.36"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192527"},{"key":"e_1_3_2_1_15_1","volume-title":"Analysis of Boolean Functions","author":"O'Donnell Ryan","unstructured":"Ryan O'Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press, USA. isbn:1107038324"},{"key":"e_1_3_2_1_16_1","unstructured":"M.D. Plummer and L. Lov\u00e1sz. 1986. Matching Theory. Elsevier Science. isbn:9780080872322"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803747"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139058520"},{"key":"e_1_3_2_1_19_1","volume-title":"Vazirani","author":"Tr\u00f6bst Thorben","year":"2020","unstructured":"Thorben Tr\u00f6bst and Vijay V. Vazirani. 2020. A Real Polynomial for Bipartite Graph Minimum Weight Perfect Matchings. arxiv:2003.08917 [cs.DM]"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217031"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3451002","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451002","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451002"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":20,"alternative-id":["10.1145\/3406325.3451002","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451002","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"}}]}}