Data Streams: Random Order & Multiple Passes

https://people.cs.umass.edu/~mcgregor/slides/09-barbados2.pdf
به جای مدل رقیب (adversary) و اگر بشود فرض کرد که جویبار داده به ترتیب تصادفی داده می‌شود (همان داده‌ها هستند اما ترتیبشان تصادفی است. مثلاً اگر بدترین حالت خیلی به ترتیب داده‌ها بستگی داشته باشد، ممکن است حذف شود) می‌شود به کران پایین‌های بهتری رسید.

در این ارائه trade-off بین تعداد عبورها و حافظه بحث می‌شود و از مسئله‌ی Index استفاده می‌شود.

مسئله‌ی 2level index هم جالب بود: بر خلاف ایندکس معمولی، آلیس این بار t تا عدد tبیتی دارد (x^..ها) و باب t عدد بین 1 تا t دارد (y) و چارلی یک عدد بین ۱ تا t دارد (i). در واقع چارلی یکی از اعداد آلیس را انتخاب می‌کند و باب به ازای هر عدد یک اندیس دارد که می‌فرستد. این مسئله با ۲ راند حداقل به t بیت تبادل داده نیاز دارد.