Essential positive covers of the cube

Linial and Radhakrishnan introduced the following problem. A pair (a,c) with a∈Rn and c∈R defines the hyperplane {x:∑iaixi=c}⊂Rn. Say that a collection of hyperplanes (a1,c1),…,(am,cm) is an essential cover of the cube {0,1}n if it is a cover, with no redundant hyperplanes, and every co-ordinate used: i.e., every point in {0,1}n is contained in some hyperplane; for every j∈[m] there exists x∈{0,1}n such that x is contained only in (aj,cj); and for every i∈[n] there exists j∈[m] with . What is the minimum size of an essential cover? Linial and Radhakrishnan showed that the answer lies between and ⌈n/2⌉+1. We give a best possible bound for the case where for every i,j. Additionally, we reduce the original problem to a conjecture concerning permanents of matrices.