{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T16:53:23Z","timestamp":1773420803359,"version":"3.50.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"ANR-France","award":["ANR-17-CE40-0022, ANR-18-IdEx-0001"],"award-info":[{"award-number":["ANR-17-CE40-0022, ANR-18-IdEx-0001"]}]},{"DOI":"10.13039\/\"https:\/\/doi.org\/10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["Nos. 12301444"],"award-info":[{"award-number":["Nos. 12301444"]}],"id":[{"id":"10.13039\/\"https:\/\/doi.org\/10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"Fundamental Research Funds for the Central Universities, Nankai University.","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"\n Using spectral techniques, H. Huang proved that every subgraph of\n \n \\(H_n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , the hypercube of dimension\n n<\/jats:italic>\n , induced on more than half the vertices has maximum degree at least\n \n \\(\\sqrt {n}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Combined with earlier work, this completed a proof of the sensitivity conjecture. In this work we show how to derive Huang\u2019s result using linear dependency and independence of vectors associated with the vertices of the hypercube. Our approach leads to several improvements of Huang\u2019s result. In particular, we prove that in any induced subgraph of\n \n \\(H_n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n with more than half the number of vertices, there are two vertices, one of odd parity and the other of even parity, each with at least\n n<\/jats:italic>\n vertices at distance at most 2. As an application, we show that for any Boolean function\n f<\/jats:italic>\n , the polynomial degree of\n f<\/jats:italic>\n is bounded above by\n \n \\(\\text{s}_0(f) \\text{s}_1(f)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , a statement which implies the sensitivity conjecture (but not immediately implied by the sensitivity conjecture). Using these linear dependencies, we show structural relations about the neighborhoods on the induced subgraphs at distance at most three.\n <\/jats:p>\n \n \n A key implement in Huang\u2019s proof is to assign signs (\n \n \\(+,-\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ) to the edges of\n \n \\(H_n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such that the product of the signs on each 4-cycle is\n \n \\(-\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . With the set of negative edges being called a signature, one may observe that there are a total of\n \n \\(2^{2^n-1}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such signatures on\n \n \\(H_n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n satisfying this condition and that the symmetric difference of any two such signatures is an edge cut. A question of high interest then is to find the smallest size among all these signatures. This is known as the frustration index in the study of signed graphs. Here we provide lower and upper bounds for this parameter, observing that the two bounds match when\n n<\/jats:italic>\n is a power of 4. We then establish a strong connection with other studies: On one hand with a question of Erd\u0151s on the number of edges of a largest 4-cycle free subgraph of the hypercube. On the other hand with Ambainis functions which are used to show a separation between degree and adversary lower bounds on query complexity.\n <\/jats:p>","DOI":"10.1145\/3777401","type":"journal-article","created":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T11:53:08Z","timestamp":1765885988000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sensitivity conjecture and signed hypercubes"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-2304-4625","authenticated-orcid":false,"given":"Sophie","family":"Laplante","sequence":"first","affiliation":[{"name":"IRIF: Institut de Recherche en Informatique Fondamentale","place":["Paris, France"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6882-6034","authenticated-orcid":false,"given":"Reza","family":"Naserasr","sequence":"additional","affiliation":[{"name":"IRIF: Institut de Recherche en Informatique Fondamentale","place":["Paris, France"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9635-8944","authenticated-orcid":false,"given":"Anupa","family":"Sunny","sequence":"additional","affiliation":[{"name":"IRIF: Institut de Recherche en Informatique Fondamentale","place":["Paris, France"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4722-4880","authenticated-orcid":false,"given":"Zhouningxin","family":"Wang","sequence":"additional","affiliation":[{"name":"IRIF: Institut de Recherche en Informatique Fondamentale","place":["Paris, France"]}]}],"member":"320","published-online":{"date-parts":[[2026,2,24]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","unstructured":"Bahman Ahmadi Fatemeh Alinaghipour Michael S. Cavers Shaun Fallat Karen Meagher and Shahla Nasserasr. 2013. Minimum number of distinct eigenvalues of graphs. Electronic Journal of Linear Algebra 26 45 (2013) 673\u2013691. DOI:10.13001\/1081-3810.1679","DOI":"10.13001\/1081-3810.1679"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","unstructured":"Andris Ambainis. 2006. Polynomial degree vs. quantum query complexity. Journal of Computer and System Sciences 72 2 (2006) 220\u2013238. DOI:10.1016\/j.jcss.2005.06.006","DOI":"10.1016\/j.jcss.2005.06.006"},{"key":"e_1_3_2_4_2","unstructured":"Arie Bialostocki. 1983. Some Ramsey-type results regarding the graph of the n-cube. Ars Combinatoria 16-A (1983) 39\u201348."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","unstructured":"Peter Brass Heiko Harborth and Hauke Nienborg. 1995. On the maximum number of edges in a c4-free subgraph of qn. Journal of Graph Theory 19 1 (1995) 17\u201323. arXiv:https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.3190190104DOI:10.1002\/jgt.3190190104","DOI":"10.1002\/jgt.3190190104"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","unstructured":"Harry Buhrman and Ronald de Wolf. 2002. Complexity measures and decision tree complexity: A survey. Theoretical Computer Science 288 1 (Oct.2002) 21\u201343. DOI:10.1016\/S0304-3975(01)00144-X","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","unstructured":"F. R. K. Chung Zolt\u00e1n F\u00fcredi R. L. Graham and P. Seymour. 1988. On induced subgraphs of the cube. Journal of Combinatorial Theory Series A 49 1 (1988) 180\u2013187. DOI:10.1016\/0097-3165(88)90034-9","DOI":"10.1016\/0097-3165(88)90034-9"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","unstructured":"A. M. Cohen and Jacques Tits. 1985. On generalized hexagons and a near octagon whose lines have three points. European Journal of Combinatorics 6 1 (1985) 13\u201327. DOI:10.1016\/S0195-6698(85)80017-2","DOI":"10.1016\/S0195-6698(85)80017-2"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802196"},{"key":"e_1_3_2_10_2","unstructured":"Paul Erd\u00f6s. 1991. Problems and results in combinatorial analysis and combinatorial number theory. In Graph theory Combinatorics and Applications Vol. 1 (Kalamazoo MI 1988). Wiley New York 397\u2013406."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","unstructured":"Chris Godsil Maxwell Levit and Olha Silina. 2021. Graph covers with two new eigenvalues. European J. Combin. 93 Article No. 103280 (2021) 12. 10.1016\/j.ejc.2020.103280","DOI":"10.1016\/j.ejc.2020.103280"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","unstructured":"C. Gotsman and N. Linial. 1992. The equivalence of two problems on the cube. Journal of Combinatorial Theory Series A 61 1 (1992) 142\u2013146. DOI:10.1016\/0097-3165(92)90060-8","DOI":"10.1016\/0097-3165(92)90060-8"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.gs.2011.004"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250867"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","unstructured":"Hao Huang. 2019. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. Annals of Mathematics 190 3 (2019) 949\u2013955. Retrieved from10.4007\/annals.2019.190.3.6","DOI":"10.4007\/annals.2019.190.3.6"},{"key":"e_1_3_2_16_2","unstructured":"Donald E. Knuth. 2019. A computational proof of Huang\u2019s degree theorem. Retrieved from https:\/\/www.cs.stanford.edu\/knuth\/papers\/huang.pdfManuscript 28 July revised 3 August https:\/\/www.cs.stanford.edu\/knuth\/papers\/huang.pdf"},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","unstructured":"Sophie Laplante Troy Lee and Mario Szegedy. 2006. The quantum adversary method and classical formula size lower bounds. Computational Complexity 15 2 (2006) 163\u2013196.","DOI":"10.1007\/s00037-006-0212-7"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","unstructured":"Daniel V. Mathews. 2019. The sensitivity conjecture induced subgraphs of cubes and Clifford algebras. J. Eur. Math. Soc. (JEMS) 24 12 (2022) 4201\u20134205. 10.4171\/jems\/1180","DOI":"10.4171\/jems\/1180"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73038"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129757"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","unstructured":"Noam Nisan and Mario Szegedy. 1994. On the degree of boolean functions as real polynomials. Computational Complexity 4 4 (Dec.1994) 301\u2013313.","DOI":"10.1007\/BF01263419"},{"key":"e_1_3_2_22_2","volume-title":"A Lower Time-bound for Parallel Random Access Machines without Simultaneous Writes","author":"Reischuk R\u00fcdiger","year":"1982","unstructured":"R\u00fcdiger Reischuk. 1982. A Lower Time-bound for Parallel Random Access Machines without Simultaneous Writes. Technical Report. Technical Report RJ3431, IBM, New York."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","unstructured":"David Rubinstein. 1995. Sensitivity vs. block sensitivity of boolean functions. Combinatorica 15 2 (01 June1995) 297\u2013299. DOI:10.1007\/BF01200762","DOI":"10.1007\/BF01200762"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422485"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","unstructured":"Thomas Zaslavsky. 1982. Signed graphs. Discrete Applied Mathematics 4 1 (1982) 47\u201374. DOI:10.1016\/0166-218X(82)90033-6","DOI":"10.1016\/0166-218X(82)90033-6"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3777401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T15:02:08Z","timestamp":1773414128000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3777401"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,24]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3777401"],"URL":"https:\/\/doi.org\/10.1145\/3777401","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,24]]},"assertion":[{"value":"2023-03-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}