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.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

We describe an explicit and simple subset of the discrete hypercube that cannot be exactly covered by a number of hyperplanes that is less than exponential. The proof exploits a connection to communication complexity and heavily relies on Razborov's lower bound for disjointness.