اثبات کران پایین برای مدل جویباری با چند بار دیدن داده‌ها

مرجع: http://www.cis.upenn.edu/~sudipto/mypapers/finalv.pdf

مسایل زیادی وجود دارند که از آنها می‌شود استفاده کرد:
۱- multi-round communication of multi-player set-disjointness: این مسئله کران پایین به صورت حاصل ضرب تعداد راندها و اندازه‌ی حافظه مورد نیاز می‌دهد.
۲- pointer jumping problems
۳- greater-than problem
در این دو مسئله‌ی آخر دو ایراد وجود دارد: یکی اینکه به دست آوردن کران پایین tight سخت است و دیگری اینکه برای توابعی که ترتیب دارند به دست آوردن الگوریتم جویباری با چند عبور سخت است. در این مسایل از روشی به نام round-elimination استفاده می‌شود که آنها را مستقل از تعداد بارهای عبور می‌کند و با اصلاح آن می‌شود این مشکلات را حل کرد.
۴- Sparse Set Disjointness Problem:
http://www.mit.edu/~mahabadi/SetCoverStreaming.pdf
باز هم در این مورد:
http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/lectures/l05.pdf
http://www.cs.umd.edu/~hajiagha/ALB14/scribe-11-11-2014.pdf
http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec10/lec10.pdf
http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic6/lectureNotes/lec10/lec10.pdf