Abstract.
We consider nondeterministic D-way branching programs computing
functions f:D^n--{0,1} in time at most kn for k<<\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--{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.
.