(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
We continue the study of the communication complexity of gap cycle counting problems. These problems have been introduced by Verbin and Yu [SODA 2011] and have found numerous applications in proving streaming lower bounds. In the noisy gap cycle counting problem (NGC), there is a small integer $k \g...
Kaydedildi:
| Asıl Yazarlar: | , |
|---|---|
| Materyal Türü: | Makale |
| Baskı/Yayın Bilgisi: |
2023
|
| Konular: | |
| Online Erişim: | https://arxiv.org/abs/2305.11053 http://arxiv.org/abs/2305.11053 |
| Etiketler: |
Etiket eklenmemiş, İlk siz ekleyin!
|