arXiv (Cornell University)
Slicing the hypercube is not easy
February 2021 • Gal Yehuda, Amir Yehudayoff
We prove that at least $Ω(n^{0.51})$ hyperplanes are needed to slice all edges of the $n$-dimensional hypercube. We provide a couple of applications: lower bounds on the computational complexity of parity, and a lower bound on the cover number of the hypercube by skew hyperplanes.