Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-148 | 3rd November 2021 00:18

Explicit Exponential Lower Bounds for Exact Hyperplane Covers

RSS-Feed




TR21-148
Authors: Benjamin Diamond, Amir Yehudayoff
Publication: 3rd November 2021 13:39
Downloads: 262
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint