Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR96-037 | 14th June 1996 00:00

TR96-037
Authors: Stasys Jukna, Alexander Razborov
Publication: 14th June 1996 15:23
Keywords:

Abstract:

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