Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

The study of the computational power of randomized

computations is one of the central tasks of complexity theory. The

main goal of this paper is the comparison of the power of Las Vegas

computation and deterministic respectively nondeterministic

computation. We investigate the power of Las Vegas computation for ...
more >>>

Juraj Hromkovic, Georg Schnitger

The investigation of the computational power of randomized

computations is one of the central tasks of current complexity and

algorithm theory. This paper continues in the comparison of the computational

power of LasVegas computations with the computational power of deterministic

and nondeterministic ones. While for one-way ...
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 >>>