Grocery on Distributed Algorithms

C1: An MIS Lower bound in Semi-Streaming Model

Reminder: This post contains 365 words · 2 min read · by Xianbin

It’s much more important today to be able to become an expert in a brand-new field in nine to twelve months than to have studied the right thing a long time ago. — Eric Jorgenson.

To be continued…

Reference

[1]. Assadi, S., Konrad, C., Naidu, K.K. and Sundaresan, J., 2024, June. O (log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (pp. 847-858).