A lower bound for essential covers of the cube
share
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 Ω(n^0.5). Later on, this notion found several applications in complexity theory. We improve the lower bound to Ω(n^0.52), and describe two applications.
READ FULL TEXT