文章基本信息

标题：Neither Reading Few Bits Twice nor Reading Illegally Helps Much
本地全文：下载
作者：Stasys Jukna ; Alexander Razborov
期刊名称：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.