Composable Core-sets for Determinant Maximization Problems via Spectral Spanners

منبع: https://arxiv.org/abs/1807.11648

مزیت دانشگاه

تنها مزیت دانشگاه برای تحقیق این است که آدمهایی اطرافت هستند که می‌توانی باهاشون کار علمی انجام بدهی. حالا وقتی این مزیت را حذف کنی دقیقاً چیزی نمی‌ماند.
قشنگ حس می‌کنم که تفاوت بین حالتی که با یک نفر دیگر روی مسئله کار می‌کنم و وقتی تنها روی مسئله کار می‌کنم چقدر زیاد است، حتی اگر آن نفر دیگر اصلاً فیلدش مرتبط نباشد و هیچ کار مثبتی هم انجام ندهد.
بدترین قسمتش این است که قوانین و آدمها هم این وضع بد را تشدید می‌کنند. آدمها بیشتر از نظر اینکه هیچ دیدی نسبت به کار گروهی ندارند و قوانین از این نظر که مثلاً توی یک کار تحقیقاتی ترتیب نویسنده‌ها است که مشخص می‌کند میزان مشارکت آنها چقدر بوده است، حتی اگر برابر باشد. تقریباً راهی برای تشخیص اینکه در یک کار گروهی چه کسی بیشتر یا کمتر کار کرده وجود ندارد، چون نمی‌شود بر اساس نتیجه شمرد، نمی‌شود بر اساس وقت یا سواد شمرد (نفر ساعت؟)، و نمی‌شود بین ایده‌ی اولیه و اثبات اولویت گذاشت. اینکه هیچ امکان اعتمادی هم نیست، و آدم نمی‌تواند مقاله را برای نقد اولیه به کسی بدهد بخواند هم بدتر است.
ابزار مناسب هم نیست، مثلاً برای پیاده‌سازی آدم باید خودش برود همه‌ی جزئیات را بخواند و یاد بگیرد، بعد همه را بخرد و بسازد و پیاده‌سازی کند تا یک نتیجه‌ی ساده را به صورت عملی نشان بدهد. در حالی که باید دانشگاه این زیرساخت‌ها را آماده می‌کرد. حداکثر حاضرند پول بدهند برای تجهیزات. خب چه کسی باید این‌ها را سر هم کند؟ هزینه‌ی نیروی انسانی کمتر از این نیست. یک سری کارها را نمی‌شود با چند نفر آدم انجام داد. حتی یک دانشگاه هم نمی‌تواند انجام بدهد و اکثر دانشگاه‌های دنیا هم آماده می‌خرند. مثل همین زیرساخت ابر که کار ما گیر آن است.
بعد خب دانشجوها هم مجبورند، می‌خواهند فارغ التحصیل بشوند. نتیجه این می‌شود که به زور یک چیزی سر هم می‌کنند تحویل می‌دهند. حالا ثابت کردن اینکه این کار نمی‌کند یا ربطی به کاری قرار بوده انجام شود ندارد به کنار، که گسترش تقلب را مدیون آن هستیم، آخرش آن آدم در جایگاه بالاتری قرار می‌گیرد و مثلاً باید ادامه‌ی کار را پیش ببرد یا به بقیه یاد بدهد.
یعنی می‌شود بدون تقلب جان سالم از اینجا به در برد؟

CSE 599: Recent Developments in Approximation Algorithms

https://homes.cs.washington.edu/~shayan/courses/cse599/index.html

CSE 599: Counting and Sampling

https://homes.cs.washington.edu/~shayan/courses/cse599-s/index.html

Differential Privacy

https://privacytools.seas.harvard.edu/differential-privacy
https://link.springer.com/chapter/10.1007/978-3-642-13059-5_55

Complexity Zoo

این یک سایت است که یک سری از کلاس‌های پیچیدگی را توضیح داده:
https://complexityzoo.uwaterloo.ca/Complexity_Zoo

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

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

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

تفاوت coreset و sketch

https://www.cs.utah.edu/~jeffp/papers/chap48-coreset+sketch.pdf

مجموعه‌ی هسته (coreset) یک مجموعه‌ی داده‌ی کاهش داده شده است که می‌توان همان الگوریتم را روی آن اجرا کرد. در اکثر موارد زیرمجموعه‌ای از ورودی است.

مجموعه‌ی هسته‌ی وزن‌دار (weighted coreset) یک مجموعه‌ی هسته است که به نقاط وزن داده شده است که می‌تواند با وزن اولیه آنها متفاوت باشد.

مجموعه‌ی هسته‌ی ضعیف (weak coreset) برای یک مجموعه از پرسه‌ها (query) تعریف می‌شود که یک شرط را تقریباً برای بعضی از پرسه‌ها بهینه می‌کند.

مجموعه‌ی هسته‌ی قوی (strong coreset) برای همه‌ی پرسه‌های یک مجموعه‌ی داده شرط را بهینه می‌کند.

----------

خلاصه (sketch) یک تصویر فشرده شده از همه‌ی داده‌های یک داده‌ساختار است که می‌تواند به سادگی به روز رسانی شود و داده‌های آن تغییر کند و به آن داده‌ی جدید اضافه شود. همچنین پرسه‌های خاصی برای آن تعریف می‌شود که ویژگی‌هایی از کل داده‌ها را تقریب می‌زند.

خلاصه خطی (linear sketch) خلاصه‌ای است که تصویر داده‌ها تابعی خطی از هر داده است، در نتیجه اضافه، حذف و تغییر را ساده‌تر می‌کند.

--------

شباهت هر دو در این است که اندازه‌ی آنها تابعی از ضریب تقریب است و نه اندازه‌ی ورودی. هرچند در برخی موارد وابستگی لگاریتمی به اندازه ورودی دارد.

تعداد حالت‌های ساخت مجموعه‌ها با شرط روی اندازه اشتراک

این سوال در الگوریتم میکاوا برای انحصار متقابل توزیع شده و در الگوریتم محاسبه‌ی فرکانس هست.
https://cseweb.ucsd.edu/classes/wi09/cse223a/p145-maekawa.pdf
https://ac.els-cdn.com/S0022000097915452/1-s2.0-S0022000097915452-main.pdf?_tid=17567bfe-0830-11e8-98fd-00000aab0f02&acdnat=1517586508_dc4612d9ce69164d6268953577dd6e24
راه‌حلی که به نظر من می‌رسد این است که اول تعداد حالت‌های اشتراک مجموعه‌ها را بسازیم، بعد عناصر را توی آنها بچینیم.
کلاً شمارش آن تا وقتی دو تا مجموعه باشد خیلی سخت نیست، مشکل از وقتی شروع می‌شود که اشتراک سه تا مجموعه که توی سوال برایش هیچ شرطی گذاشته نشده چه چیزی باید باشد.
خب توی خود مقاله نوشته است که در نظریه کدگذاری این بحث شده.
این داستان ادامه دارد...

Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem

https://arxiv.org/abs/1801.02793