Slicing the hypercube is not easy

Abstract

We prove that at least $\Omega (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.

arXiv comment20 pages

References in corpus (1)

• The plank problem for symmetric bodies

Cited by in corpus (2)

• A lower bound for essential covers of the cube
• Depth lower bounds in Stabbing Planes for combinatorial principles