ECCC-Report TR96-037https://eccc.weizmann.ac.il/report/1996/037Comments and Revisions published for TR96-037en-usFri, 14 Jun 1996 15:23:50 +0300
Paper TR96-037
| Neither Reading Few Bits Twice nor Reading Illegally Helps Much |
Stasys Jukna,
Alexander Razborov
https://eccc.weizmann.ac.il/report/1996/037
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^{\Omega(\min\{d_1, d_2/s\})}$, where $d_1$ and $d_2$ are the
minimal distances of $C$ and its dual $C^{\perp}.$ We apply this
criterion to explicit linear codes and obtain a super-polynomial
lower bound for $s=o(n/\log n).$
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.
Fri, 14 Jun 1996 15:23:50 +0300https://eccc.weizmann.ac.il/report/1996/037