Chennai Mathematical Institute

Seminars




Computer Science Seminar
Date: Tuesday, 27 August 2024
Time: 11:50 AM
Venue: Seminar Hall
A new information complexity measure for streaming algorithms

Sumegha Garg
Rutgers University.
27-08-24


Abstract

In this talk, we will introduce a new notion of information complexity for one-pass and multi-pass streaming problems, and use it to prove memory lower bounds for the coin problem. In the coin problem, one sees a stream of 𝑛 i.i.d. uniform bits and one would like to compute the majority (or sum) with constant advantage. We show that any constant pass algorithm must use Ω(log 𝑛) bits of memory. This information complexity notion is also useful to prove tight space complexity for the needle problem, which in turn implies tight bounds for the problem of approximating higher frequency moments in a data stream.

Joint works with Mark Braverman, Qian Li, Shuo Wang, David P. Woodruff and Jiapeng Zhang.