Требования к хранилищу для медианного выбора (двухпроходные алгоритмы)

В классической статье Манро и Патерсон изучают проблему того, сколько памяти требуется алгоритму для нахождения медианы в случайно отсортированном массиве. В частности, они ориентированы на следующую модель:

ввод читается слева направо в течение числа P раз.

Показано, что $O(n^{\frac{1}{2P}})$ ячеек памяти достаточно, но соответствующая нижняя граница известна только для P = 1. Я не видел никакого результата для P> 1. Кто-нибудь знает о таких нижних границах?

Обратите внимание, что основная трудность здесь заключается в том, что на втором проходе вход больше не упорядочен случайным образом.

Попробуйте эту статью Чана в недавней SODA: http://portal.acm.org/citation.cfm?id=1721842&dl=ACM .

Быстрый поиск в Google также нашел следующую статью, которая выглядит, возможно, актуальной, но я ее еще не читал: http://portal.acm.org/citation.cfm?id=1374470 .

Первой статьей, доказывающей границы для более чем одного прохода, была моя статья с Джайрамом и Амитом из SODA'08. Затем есть статья, упомянутая Уорреном, которая улучшает границы благодаря более чистому доказательству.

Короче говоря, мы понимаем зависимость, если вы разрешите постоянные перед числом проходов. Конечно, эти константы находятся в показателе степени, поэтому вы можете попросить точного понимания. Моя главная жалоба заключается в том, что модель многопроходной потоковой передачи не так уж хорошо мотивирована.

Более интригующий вопрос - можем ли мы доказать нижнюю границу программы ветвления. Может ли быть так, что даже для алгоритма ограниченного пространства, который может обращаться к памяти по своему усмотрению, лучшая стратегия состоит в том, чтобы просто выполнять многопроходную потоковую передачу?

Ответ представляется утвердительным, и у нас есть некоторый частичный прогресс в его доказательстве.