Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR21-148 | 7th September 2022 16:31

Explicit Exponential Lower Bounds for Exact Hyperplane Covers

RSS-Feed




Revision #1
Authors: Benjamin Diamond, Amir Yehudayoff
Accepted on: 7th September 2022 16:31
Downloads: 213
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.


Paper:

TR21-148 | 3rd November 2021 00:18

Explicit Exponential Lower Bounds for Exact Hyperplane Covers





TR21-148
Authors: Benjamin Diamond, Amir Yehudayoff
Publication: 3rd November 2021 13:39
Downloads: 794
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