Jayram S. Thathachar

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 >>>

Miklos Ajtai

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 >>>

Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

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 >>>

Dmytro Gavinsky

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 >>>