  For a decision problem from coding theory, we prove a quadratic expected
time-space tradeoff of the form $\eT\eS=\Omega(\tfrac{n^2}{q})$ for $q$-way
deterministic decision branching programs, where $q\geq 2$. Here $\eT$ is the
expected computation time and $\eS$ is the expected space, when all inputs are
equally likely. This bound is to our knowledge, the first such to show an
exponential size requirement whenever $\eT = O(n^2)$. Previous exponential size
tradeoffs for Boolean decision branching programs were valid for
time-restricted models with $T=o(n\log_2{n})$. Proving quadratic time-space
tradeoffs for unrestricted time decision branching programs has been a major
goal of recent research -- this goal has already been achieved for
multiple-output branching programs two decades ago. We also show the first
quadratic time-space tradeoffs for Boolean decision branching programs
verifying circular convolution, matrix-vector multiplication and discrete
Fourier transform. Furthermore, we demonstrate a constructive Boolean decision
function which has a quadratic expected time-space tradeoff in the Boolean
deterministic decision branching program model. When $q$ is a constant the
tradeoff results derived here for decision functions verifying various
functions are order-comparable to previously known tradeoff bounds for
calculating the corresponding multiple-output functions.
