We obtain an exponential separation between consecutive
levels in the hierarchy of classes of functions computable by
polynomial-size syntactic read-k-times branching programs, for
{\em all\/} k>0, as conjectured by various
authors~\cite{weg87,ss93,pon95b}. For every k, we exhibit two
explicit functions that can be computed by linear-sized
read-(\kpluso)-times branching programs but ...
more >>>
Our computational model is a random access machine with n
read only input registers each containing c \log n bits of
information and a read and write memory. We measure the time by the
number of accesses to the input registers. We show that for all k
there is ...
more >>>
We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifi cally, letting n denote the input length, we construct a delegation scheme for any language veri fiable in non-deterministic time and space (T(n);S(n)) with communication complexity poly(S(n)), verifi er ... more >>>
We define and study the model of patterned non-determinism in bipartite communication complexity, denoted by PNP^{X\leftrightarrow Y}.
It generalises the known models UP^{X\leftrightarrow Y} and FewP^{X\leftrightarrow Y} through relaxing the constraints on the witnessing structure of the underlying NP^{X\leftrightarrow Y}-protocol.
It is shown that for the case of total functions ...
more >>>