کران پایین در مدل جویبار داده با پیچیدگی ارتباطات

مرجع: فیلم کلاس دکتر آبام (مکتب‌خونه گذاشته)
سوال ۱: آلیس و باب هر کدام یک رشته دارند، می‌خواهیم ببینیم اینها با هم مساوی هستند یا نه. دنبال راه حل تصادفی هستیم که کمتر از خطی تبادل داده داشته باشیم. من فکر کردم که یک تعدادی از بیت‌ها را به صورت تصادفی انتخاب کنیم و بفرستیم، مشکل این خواهد بود که فرستادن همان بیت‌ها حجمش زیاد خواهد بود. log n بیت برای اندیس هر کدام لازم است که برای k تا می‌شود k log n. احتمال اینکه درست تشخیص بدهیم هم می‌شود k/n. برای رسیدن به همان احتمال ثابت ۱/۳ هم لازم است که k=n/3 باشد یعنی n/3 log n که از n هم بیشتر می‌شود! پس اینجا معجزه‌ی نظریه اعداد را می‌بینیم که با انتخاب یک عدد اول می‌آید همین کار را با log n بیت انجام می‌دهد.

سوال ۲: اینکه ما یک قسمت از ورودی را می‌دهیم دست آلیس و یک قسمت را دست باب و می‌گوییم الگوریتم را اجرا کنیم و مقدار حافظه‌اش را بفرستیم مثل این است که تا یک زمان از اجرا را به آلیس بدهیم و بقیه را به باب. بعدش هم اینکه بخواهیم کاری کنیم که آن کسی که اندیسش را باب دارد عنصر با بیشتر از n/2 تکرار بشود باید همه‌ی اندیس‌ها را بنویسیم و این اندیس را n/2 بار تکرار کنیم. از روی داده‌ها می‌شود فهمید هر قسمت را باید چه کسی انجام بدهد چون اندیس را فقط آلیس دارد باید n/2 تکرار را آلیس انجام دهد و بقیه را بدهیم به باب.