The complexity theory for black-box algorithms, introduced by
Droste et al. (2006), describes common limits on the efficiency of
a broad class of randomised search heuristics. There is an
obvious trade-off between the generality of the black-box model
and the strength of the bounds that can be proven in such ... more >>>

The class NC$^1$ of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$ and L based on counting functions or, ... more >>>

The deterministic space complexity of approximating the length of the longest increasing subsequence of
a stream of $N$ integers is known to be $\widetilde{\Theta}(\sqrt N)$. However, the randomized
complexity is wide open. We show that the technique used in earlier work to establish the $\Omega(\sqrt
N)$ deterministic lower bound fails ... more >>>