Slicing the hypercube is not easy

MaRDI QIDQ6360322zbMATH OpenFDO

Authors Gal Yehuda, Amir Yehudayoff

Publication date 10 February 2021

Mathematics Subject Classification ID

Extremal set theory (05D05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

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.

This page was built for publication: Slicing the hypercube is not easy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6360322)