Neither reading few bits twice nor reading illegally helps much Original Research Article

We first consider the so-called (1, +s)-branching programs in which along every consistent path at most s variables are tested more than once. We prove that any such program computing a characteristic function of a linear code C has size at least 2Ω(min/s d1, d2s), where d1 and d2 are the minimal distances of C and its dual C⊥. We apply this criterion to explicit linear codes and obtain a super-polynomial lower bound for s = o(nlogn).