Randomized search heuristics like local search, simulated annealing or all kinds of evolutionary algorithms have many applications. However, for most problems the best worst-case expected run times are achieved by more problem-specific algorithms. This raises the question about the limits of general randomized search heuristics.

Here a framework called black-box ... more >>>

We study the problem of representing symmetric Boolean functions as symmetric polynomials over Z_m. We show an equivalence between such
representations and simultaneous communication protocols. Computing a function with a polynomial of degree d modulo m=pq is equivalent to a two player protocol where one player is given the first ... more >>>

We strengthen an earlier notion of
resource-bounded Baire's categories, and define
resource bounded Baire's categories on small complexity classes such as P, QP, SUBEXP
and on probabilistic complexity classes such as BPP.
We give an alternative characterization of meager sets via resource-bounded
Banach Mazur games.
We show that the class ... more >>>