A lower bound for essential covers of the cube

Gal Yehuda, Amir YehudayoffComb 2021 · DOI · OpenReview

Abstract: Essential covers were introduced by Linial and Radhakrishnan as a model that captures two complementary properties: (1) all variables must be included and (2) no element is redundant. In their seminal paper, they proved that every essential cover of the $n$-dimensional hypercube must be of size at least $\Omega(n^{0.5})$. Later on, this notion found several applications in complexity theory. We improve the lower bound to $\Omega(n^{0.52})$, and describe two applications.

Introduction

This research, authored by Gal Yehuda and Amir Yehudayoff, addresses a fundamental problem in combinatorial geometry and theoretical computer science. It provides the first improvement in over 15 years to the lower bound on the number of hyperplanes required to "essentially" cover the vertices of an $n$-dimensional hypercube.

In an $n$-dimensional hypercube, vertices are points where every coordinate is either $+1$ or $-1$. While a trivial cover of all $2^n$ vertices can be achieved with just two hyperplanes (e.g., $x_1 = 1$ and $x_1 = -1$), such solutions are degenerate as they ignore most dimensions. To capture more complex structures, researchers study essential covers, which must satisfy three criteria:

  1. Coverage: Every vertex must lie on at least one hyperplane.
  2. Sensitivity: Every variable (dimension) must appear in the equation of at least one hyperplane.
  3. Minimality: No hyperplane can be removed without leaving at least one vertex uncovered.

Since 2005, the best known lower bound for the size of such a cover was $\Omega(n^{0.5})$. This paper breaks that "square-root barrier," establishing a new bound of $\Omega(n^{0.52})$.

Methodology

The authors employ a proof-by-contradiction strategy: they assume a cover smaller than the proposed bound exists and then demonstrate the existence of at least one vertex that remains uncovered. This is achieved through a three-phase coordinate discovery process.

In the first two phases, the authors use matrix decomposition and anti-concentration inequalities (such as the Littlewood-Offord lemma) to fix the majority of the coordinates of a potential vertex $u$. This involves a sophisticated structural analysis of the matrix $V$, where rows represent the normal vectors of the hyperplanes in the cover.

Structural decomposition of the hyperplane normal vector matrix $V$, partitioning hyperplanes and variables by sparsity and scale.

As illustrated in the figure above, the matrix $V$ is partitioned into blocks based on "sparsity" and "scales." This decomposition allows the authors to handle different types of hyperplanes—ranging from those with many zero coefficients to those with "many scales" (vectors decomposable into parts with rapidly decreasing norms).

In the final phase, the authors resolve the remaining coordinates using a deep result from convex geometry: Bang’s solution to Tarski’s plank problem. Specifically, they apply a lemma by Keith Ball to "round" a continuous vector to a discrete hypercube vertex while ensuring it avoids all hyperplanes in the cover.

Key Insights and Results

The primary contribution of this work is the integration of tools from convex geometry—specifically the plank problem—to push past the combinatorial limits of previous techniques. By developing a structural lemma for the matrix $V$, the authors successfully handle non-generic, highly structured hyperplanes that often complicate essential cover problems.

Major Findings

  • New Lower Bound: The minimum size of an essential cover $e(n)$ is proven to be at least $\Omega(n^{0.52})$.
  • Proof Complexity Gains:
    • Stabbing Planes: The lower bound for the refutation-size of Tseitin formulas is improved from $\Omega(n)$ to $\Omega(n^{1.04})$.
  • Linear Resolution: The tree-like $Res(lin_{\mathbb{Q}})$ proof size lower bound is improved from $2^{\Omega(\sqrt{n})}$ to $2^{\Omega(n^{0.52})}$.

Conclusion

While the improvement from $0.5$ to $0.52$ is a significant theoretical breakthrough, a substantial gap remains between this new lower bound and the known upper bound of $n/2$. The authors suggest that further refinements to the structural analysis of the matrix $V$—particularly regarding how non-sparse hyperplanes interact—could eventually lead to a linear lower bound ($\Omega(n)$).

Summary updated

Abstract

Essential covers were introduced by Linial and Radhakrishnan as a model that captures two complementary properties: (1) all variables must be included and (2) no element is redundant. In their seminal paper, they proved that every essential cover of the $n$-dimensional hypercube must be of size at least $\Omega(n^{0.5})$. Later on, this notion found several applications in complexity theory. We improve the lower bound to $\Omega(n^{0.52})$, and describe two applications.
BibTeX
@article{yehuda2021lower,
  author = {Gal Yehuda and Amir Yehudayoff},
  title = {{A lower bound for essential covers of the cube}},
  journal = {Comb.},
  year = {2021},
  doi = {10.1007/s00493-024-00093-4},
}
Figure