2021/05/28 by Yehuda, Gal, Yehudayoff, Amir · 1 citation
#05D99 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1
paper · doi:10.48550/arxiv.2105.13615
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 Ω(n0.5). Later on, this notion found several applications in complexity theory. We improve the lower bound to Ω(n0.52), and describe two applications.