Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-037 | 14th June 1996 00:00

Neither Reading Few Bits Twice nor Reading Illegally Helps Much


Authors: Stasys Jukna, Alexander Razborov
Publication: 14th June 1996 15:23
Downloads: 1239


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.

ISSN 1433-8092 | Imprint