Slicing the hypercube is not easy
arXiv:2102.05536v210 citations
AI Analysis
This addresses a foundational problem in computational geometry and complexity theory, with applications to lower bounds on parity computation and hypercube covering.
The paper tackled the problem of determining the minimum number of hyperplanes required to slice all edges of an n-dimensional hypercube, proving a lower bound of Ω(n^0.51).
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.