Abstract.
We consider nondeterministic D-way branching programs computing
functions $f:D^n\to \{0,1\}$ in time at most $kn$ for $k\ll\log n$. In the
boolean case, where D={0,1}, no exponential lower bounds
are known even for k=2. Such lower bounds are known only if the
domain D is sufficiently large: at least $n^c$ in [Ajtai] and
at least $2^{2^k}$ in [Beame, Saks, Thathachar]. In this note we prove
such a lower bound for for an explicit function $f:D^n\to \{0,1\}$ over
substantially smaller domain of size about $2^k$.
Our function $f(Y,x)$ has $n^2+n$ variables, the
first $n^2$ of which are arranged in an n by n matrix Y.
The variables take their values in the domain D=GF(q), and
$f(Y,x)=1$ iff the vector $x$ is orthogonal over GF(q) to all rows of Y.
We prove that, for any prime power q\geq c4^k,
any nondeterministic
branching program computing f in time kn requires size
exponential in n/8^k.
.