Slicing the hypercube is not easy

2021/02/10 by Gal Yehuda, Yehuda, Gal, Amir Yehudayoff +1 · 1 citation
Computer Science · Engineering · #05D05 #52C35 #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #Combinatorics (math.CO) #Computational Complexity (cs.CC) #F.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #Interconnection Networks and Systems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2102.05536

openalex publication_date 2021/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• The plank problem for symmetric bodies

Cited by

• Nondegenerate hyperplane covers of the hypercube

Related

• Improved lower bound for hypercube edge slicing
• Slicing all Edges of an n-cube Requires n^2/3 Hyperplanes
• Nondegenerate hyperplane covers of the hypercube
• Covering the hypercube, the uncertainty principle, and an interpolation formula
• Partitioning the hypercube into smaller hypercubes