Lance Fortnow, Rahul Santhanam

We strengthen the non-deterministic time hierarchy theorem of

\cite{Cook72, Seiferas-Fischer-Meyer78, Zak83} to show that the lower bound

holds against sublinear advice. More formally, we show that for any constants

$c$ and $d$ such that $1 \leq c < d$, there is a language in $\NTIME(n^d)$

which is not in $\NTIME(n^c)/n^{1/d}$. ...
more >>>

Nathanael Fijalkow

The notion of online space complexity, introduced by Karp in 1967, quantifies the amount of states required to solve a given problem using an online algorithm,

represented by a machine which scans the input exactly once from left to right.

In this paper, we study alternating machines as introduced by ...
more >>>