{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:01:37Z","timestamp":1750309297991,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISIRD Grant from Sponsored Research and Industrial Consultancy, IIT Kharagpur"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n            We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Our contributions are as follows: Let\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(f : \\mathbb {F}_2^n \\rightarrow \\lbrace -1, 1\\rbrace\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            be a Boolean function with Fourier support \ud835\udcae and Fourier sparsity\n            <jats:italic>k<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3647629","type":"journal-article","created":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T13:51:42Z","timestamp":1707832302000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On parity decision trees for Fourier-sparse Boolean functions"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9520-7340","authenticated-orcid":false,"given":"Nikhil Shekhar","family":"Mande","sequence":"first","affiliation":[{"name":"University of Liverpool, Liverpool, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1546-7749","authenticated-orcid":false,"given":"Swagato","family":"Sanyal","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kharagpur, Kharagpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,10]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00063"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.755000"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3396695"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1136869"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000040"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21924"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2724704"},{"key":"e_1_3_3_9_2","article-title":"On the communication complexity of XOR functions","volume":"0909","author":"Montanaro Ashley","year":"2009","unstructured":"Ashley Montanaro and Tobias Osborne. 2009. On the communication complexity of XOR functions. CoRR abs\/0909.3392 (2009).","journal-title":"CoRR"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2019.v015a011"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0110-y"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00062"},{"key":"e_1_3_3_13_2","volume-title":"Correlation Properties of Cyclic Sequences","author":"Titsworth Robert C.","year":"1962","unstructured":"Robert C. Titsworth. 1962. Correlation Properties of Cyclic Sequences. Ph. D. Dissertation. California Institute of Technology."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.76"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3647629","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3647629","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:38Z","timestamp":1750291418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3647629"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3647629"],"URL":"https:\/\/doi.org\/10.1145\/3647629","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2022-05-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-08","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}