Andreev et al.~\cite{ABCR97} give constructions of Boolean
functions (computable by polynomial-size circuits) that require large
read-once branching program (1-b.p.'s): a function in P that requires
1-b.p. of size at least 2^{n-\polylog(n)}, a function in quasipolynomial
time that requires 1-b.p. of size at least 2^{n-O(\log n)}, and a
function in LINSPACE ... more >>>