期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We first consider so-called {\em (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(mind1d2s) , 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)
Then we introduce a natural generalization of read-k-times and
(1+s) -branching programs that we call {\em semantic branching
programs}. These programs correspond to {\em corrupting} Turing
machines which, unlike eraser machines, are allowed to read input bits
even {\em illegally}, i.e. in excess of their quota on multiple
readings, but in that case they receive in response an unpredictably
corrupted value. We generalize the above-mentioned bound to the
semantic case, and also prove exponential lower bounds for semantic
read-once nondeterministic branching programs.
