  In this paper we prowide lower bounds on the complexity of the DNF exception
problem for short exception lists and hypercube covering problem. The method
proposed is based on the relaxation of the initial problem to a certain linear
programming problem. Some explicit bounds are provided for the case when
exception list size is bounded above by a logarithm of dimension. The bound
provided in this case is significantly stronger than the bounds known before.
