TR96-037 Authors: Stasys Jukna, Alexander Razborov

Publication: 14th June 1996 15:23

Downloads: 2001

Keywords:

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.