{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:46Z","timestamp":1750220446729,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T00:00:00Z","timestamp":1616716800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61832003, 61761136014, 61872334, 61433014 and 62002229"],"award-info":[{"award-number":["61832003, 61761136014, 61872334, 61433014 and 62002229"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Strategic Priority Research Program of Chinese Academy of Sciences","award":["XDA27000000"],"award-info":[{"award-number":["XDA27000000"]}]},{"name":"973 Program of China","award":["2016YFB1000201"],"award-info":[{"award-number":["2016YFB1000201"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            In this article, we investigate the sensitivity complexity of hypergraph properties. We present a\n            <jats:italic>k<\/jats:italic>\n            -uniform hypergraph property with sensitivity complexity\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            (\u2308\n            <jats:italic>k\/3<\/jats:italic>\n            \u2309) for any\n            <jats:italic>k<\/jats:italic>\n            \u2265\n            <jats:italic>3<\/jats:italic>\n            , where\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices. Moreover, we can do better when\n            <jats:italic>k<\/jats:italic>\n            \u2261\n            <jats:italic>1<\/jats:italic>\n            (mod 3) by presenting a\n            <jats:italic>k<\/jats:italic>\n            -uniform hypergraph property with sensitivity\n            <jats:italic>O<\/jats:italic>\n            (n\u2308\n            <jats:italic>k\/3<\/jats:italic>\n            \u2309-1\/2). This result disproves a conjecture of Babai, which conjectures that the sensitivity complexity of\n            <jats:italic>k<\/jats:italic>\n            -uniform hypergraph properties is at least \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            <jats:italic>\n              <jats:sup>k\/2<\/jats:sup>\n            <\/jats:italic>\n            ). We also investigate the sensitivity complexity of other symmetric functions and show that for many classes of transitive Boolean functions the minimum achievable sensitivity complexity can be\n            <jats:italic>O<\/jats:italic>\n            (N\n            <jats:sup>1\/3<\/jats:sup>\n            ), where\n            <jats:italic>N<\/jats:italic>\n            is the number of variables.\n          <\/jats:p>","DOI":"10.1145\/3448643","type":"journal-article","created":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T16:31:02Z","timestamp":1616776262000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Sensitivity Complexity of\n            <i>k<\/i>\n            -Uniform Hypergraph Properties"],"prefix":"10.1145","volume":"13","author":[{"given":"Qian","family":"Li","sequence":"first","affiliation":[{"name":"Shenzhen University, Shenzhen, China"}]},{"given":"Xiaoming","family":"Sun","sequence":"additional","affiliation":[{"name":"University of Chinese Academy of Sciences, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2021,3,26]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"116","article-title":"New separation between s(f) and bs(f)","volume":"18","author":"Ambainis Andris","year":"2011","unstructured":"Andris Ambainis and Xiaoming Sun . 2011 . New separation between s(f) and bs(f) . Electronic Colloquium on Computational Complexity 18 (2011), 116 . http:\/\/eccc.hpi-web.de\/report\/2011\/116. Andris Ambainis and Xiaoming Sun. 2011. New separation between s(f) and bs(f). Electronic Colloquium on Computational Complexity 18 (2011), 116. http:\/\/eccc.hpi-web.de\/report\/2011\/116.","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201910)","author":"Babai L\u00e1szl\u00f3","year":"2010","unstructured":"L\u00e1szl\u00f3 Babai , Anandam Banerjee , Raghav Kulkarni , and Vipul Naik . 2010 . Evasiveness and the distribution of prime numbers . In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201910) . 71--82. L\u00e1szl\u00f3 Babai, Anandam Banerjee, Raghav Kulkarni, and Vipul Naik. 2010. Evasiveness and the distribution of prime numbers. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201910). 71--82."},{"unstructured":"Joshua Biderman Kevin Cuddy Ang Li and Min Jae Song. 2015. On the sensitivity of k-uniform hypergraph properties. arXiv:1510.00354  Joshua Biderman Kevin Cuddy Ang Li and Min Jae Song. 2015. On the sensitivity of k-uniform hypergraph properties. arXiv:1510.00354","key":"e_1_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/2688073.2688085"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1016\/S0304-3975(01)00144-X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1137\/S0097539700382005"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1109\/CCC.2005.38"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/800070.802196"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1137\/0215006"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1016\/j.tcs.2012.11.006"},{"doi-asserted-by":"crossref","unstructured":"Hao Huang. 2019. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. arXiv:1907.008487  Hao Huang. 2019. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. arXiv:1907.008487","key":"e_1_2_1_11_1","DOI":"10.4007\/annals.2019.190.3.6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/2422436.2422454"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1016\/j.tcs.2014.11.012"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.4086\/cjtcs.2016.008"},{"key":"e_1_2_1_15_1","volume-title":"Young","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"2002","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Neal E . Young . 2002 . Lecture notes on evasiveness of graph properties. arXiV:cs\/0205031 L\u00e1szl\u00f3 Lov\u00e1sz and Neal E. Young. 2002. Lecture notes on evasiveness of graph properties. arXiV:cs\/0205031"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1137\/0220062"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/129712.129757"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1016\/0304-3975(76)90053-0"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1016\/j.tcs.2007.05.020"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1016\/j.tcs.2011.02.042"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/2422436.2422485"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1016\/0020-0190(84)90019-X"},{"unstructured":"Jake Wellens. 2020. Relationships between the number of inputs and other complexity measures of Boolean functions. arXiv:2005.00566  Jake Wellens. 2020. Relationships between the number of inputs and other complexity measures of Boolean functions. arXiv:2005.00566","key":"e_1_2_1_23_1"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448643","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448643","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:43Z","timestamp":1750193263000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448643"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,26]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3448643"],"URL":"https:\/\/doi.org\/10.1145\/3448643","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2021,3,26]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}