Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > BENJAMIN DIAMOND:
All reports by Author Benjamin Diamond:

TR21-148 | 3rd November 2021
Benjamin Diamond, Amir Yehudayoff

Explicit Exponential Lower Bounds for Exact Hyperplane Covers

We describe an explicit and simple subset of the discrete hypercube which cannot be exactly covered by fewer than exponentially many hyperplanes. The proof exploits a connection to communication complexity, and relies heavily on Razborov's lower bound for disjointness.

more >>>



ISSN 1433-8092 | Imprint