Section outline

  • Wykład 5. Dolne ograniczenia dla algorytmów randomizowanych: zasada minimaksowa Yao, dolne ograniczenie dla problemu pamięci podręcznej.

    • A. Fiat, R. Karp, M. Luby, L. McGeoch, D. Sleator, N. Young: Competitive paging algorithms. Journal of Algorithms, 1991
    • A. Yao: Probabilistic computations: Towards a unified measure of complexity. FOCS, 1977