Gait analysis has applications not only in medical, rehabilitation and sports, but it can also
play a decisive role in security and surveillance as a behavioral biometric factor. This paper …

We show that for any reasonable semantic model of computation and for any positive integer
a and rationals 1≤ c< d, there exists a language computable in time nd with a bits of advice …

We show that for any constant a, ZPP/b (n) strictly contains ZPTIME (na)/b (n) for some b (n)=
O (log n log log n). Our techniques are very general and give the same hierarchy for all …

For each time bound T:{input strings}→{natural numbers} that is some machine's exact
running time, there is a {0, 1}-valued function f T that can be computed within time …

Translational lemmas are stated in a general framework and then applied to specific
complexity classes. Necessary and sufficient conditions are given for every set accepted by …

We show that non-deterministic time NTIME (n) is not contained in deterministic time n/sup 2-
/spl epsiv//and polylogarithmic space, for any/spl epsiv/> 0. This implies that (infinitely often) …

Probabilistische Datenbanken und Wissensbasen werden immer wichtiger in der
Wissenschaft und Industrie. Sie werden ständig mit neuen Daten erweitert, angetrieben …

It is shown that there exists f:{0, 1\}^ n/2 * {0, 1\}^ n/2 → {0, 1\} f: 0, 1 n/2× 0, 1 n/2→ 0, 1 in E^
NP NP such that for every 2^ n/2 * 2^ n/2 2 n/2× 2 n/2 matrix M of rank ≤ ρ≤ ρ we have P …

In this paper, we introduce the hybrid query complexity, denoted as $\mathrm {Q}(f; q) $,
which is the minimal query number needed to compute $ f $, when a classical decision tree …

It is shown that NP is equal to PSPACE if and only if for every oracle set A, NP (A) is equal to
the class NPQUERY (A) of languages accepted by nondeterministic polynomial space …