Ruang Bawah-Batas Teknik Baru untuk Algoritma Streaming

Apakah kompleksitas komunikasi (CC) satu-satunya pendekatan yang dikenal untuk algoritma streaming yang batas bawahnya? Apakah ada teknik lain, bahkan jika batas bawah bersyarat ?

Secara umum, apakah kita puas dengan kemajuan yang dicapai melalui CC? Atau mencari teknik alternatif (meskipun kondisional) akan menjadi arah yang menarik?

Hasil terbaru dari Li, Nguyen, dan Woodruff menunjukkan bahwa untuk setiap algoritma streaming dalam model pintu putar (di mana aliran terdiri dari penyisipan dan penghapusan elemen) terdapat algoritma yang bekerja dengan hanya mempertahankan sketsa linier dan hanya menggunakan sedikit lebih banyak ruang . Jadi untuk membuktikan batas bawah ruang dalam model pintu putar itu (hingga beberapa faktor logaritmik) cukup untuk membuktikan batas bawah ruang untuk sketsa linier. Ini bisa lebih mudah untuk dibuktikan, misalnya dengan membuktikan komunikasi yang lebih rendah dalam model komunikasi simultan daripada dalam model satu arah, atau dengan lebih langsung bekerja dengan struktur linier sketsa: periksa kertas untuk batas bawah pada kompleksitas ruang momen frekuensi terbukti seperti ini.

Meskipun bukan hal baru, (dan tergantung pada apa yang Anda anggap sebagai "algoritma streaming"), teknik batas bawah standar adalah memilih sekumpulan input (sebesar mungkin), dan membuktikan bahwa masing-masing harus mengarahkan algoritma ke memori yang berbeda. konfigurasi. Batas bawah tersirat kemudian adalah log dari jumlah input tersebut.

$\Omega(\epsilon^{-1}\log^2 N\epsilon)$$(1+\epsilon)$$N$