Luca Trevisan

Three fundamental results of Levin involve algorithms or reductions

whose running time is exponential in the length of certain programs. We study the

question of whether such dependency can be made polynomial.

(1) Levin's ``optimal search algorithm'' performs at most a constant factor more slowly

than any other fixed ...
more >>>