{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T15:45:22Z","timestamp":1768319122137,"version":"3.49.0"},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2024,12,16]],"date-time":"2024-12-16T00:00:00Z","timestamp":1734307200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We prove a new lower bound for the almost 20-year-old problem of determining the smallest possible size of an essential cover of the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000257_inline1.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-dimensional hypercube <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000257_inline2.png\"\/><jats:tex-math>\n$\\{\\pm 1\\}^n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, that is, the smallest possible size of a collection of hyperplanes that forms a minimal cover of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000257_inline3.png\"\/><jats:tex-math>\n$\\{\\pm 1\\}^n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and such that, furthermore, every variable appears with a non-zero coefficient in at least one of the hyperplane equations. We show that such an essential cover must consist of at least <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000257_inline4.png\"\/><jats:tex-math>\n$10^{-2}\\cdot n^{2\/3}\/(\\log n)^{2\/3}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> hyperplanes, improving previous lower bounds of Linial\u2013Radhakrishnan, of Yehuda\u2013Yehudayoff, and of Araujo\u2013Balogh\u2013Mattos.<\/jats:p>","DOI":"10.1017\/s0963548324000257","type":"journal-article","created":{"date-parts":[[2024,12,16]],"date-time":"2024-12-16T09:55:39Z","timestamp":1734342939000},"page":"326-337","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Essential covers of the hypercube require many hyperplanes"],"prefix":"10.1017","volume":"34","author":[{"given":"Lisa","family":"Sauermann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zixuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,12,16]]},"reference":[{"key":"S0963548324000257_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.07.012"},{"key":"S0963548324000257_ref3","unstructured":"[3] Araujo, I. , Balogh, J. and Mattos, L. (2022) New lower bounds for essential covers of the cube, arXiv:2209.00140."},{"key":"S0963548324000257_ref5","first-page":"990","article-title":"A solution of the \u201cplank problem","volume":"2","author":"Bang","year":"1951","journal-title":"Proc. Amer. Math. Soc."},{"key":"S0963548324000257_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01245089"},{"key":"S0963548324000257_ref8","unstructured":"[8] Ivanisvili, P. , Klein, O. and Vershynin, R. (2023) Covering the hypercube, the uncertainty principle, and an interpolation formula, arXiv:2310.13277."},{"key":"S0963548324000257_ref9","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00117"},{"key":"S0963548324000257_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-024-00093-4"},{"key":"S0963548324000257_ref2","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1993.1011"},{"key":"S0963548324000257_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-4221-y"},{"key":"S0963548324000257_ref7","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548324000257_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003411"},{"key":"S0963548324000257_ref13","unstructured":"[13] Yehuda, G. and Yehudayoff, A. (2021) Slicing the hypercube is not easy, arXiv:2102.05536."},{"key":"S0963548324000257_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2013.02.002"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T05:00:48Z","timestamp":1745902848000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000257\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,16]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["S0963548324000257"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000257","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,16]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}