Slicing the hypercube is not easy Article Swipe
Gal Yehuda
,
Amir Yehudayoff
·
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2102.05536
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2102.05536
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.
Related Topics To Compare & Contrast
Vs
Mathematics
Vs
Algorithm
Concepts
Hypercube
Hyperplane
Slicing
Skew
Upper and lower bounds
Computer science
Combinatorics
Computational complexity theory
Parallel computing
Discrete mathematics
Mathematics
Algorithm
World Wide Web
Telecommunications
Mathematical analysis
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2102.05536
- https://arxiv.org/pdf/2102.05536
- OA Status
- green
- Cited By
- 4
- References
- 23
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W3128839604
All OpenAlex metadata
Raw OpenAlex JSON
No additional metadata available.