BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Sumegha Garg (Harvard) DTSTART:20201125T180000Z DTEND:20201125T190000Z DTSTAMP:20260423T021008Z UID:TCSPlus/18 DESCRIPTION:Title: The Coin Problem with Applications to Data Streams\nby Sumegha Garg ( Harvard) as part of TCS+\n\n\nAbstract\nConsider the problem of computing the majority of a stream of $n$ i.i.d. uniformly random bits. This problem \, known as the coin problem\, is central to a number of counting problems in different data stream models. We show that any streaming algorithm for solving this problem with large constant advantage (over the uniform dist ribution) must use $\\Omega(\\log n)$ bits of space. Previously\, it was k nown that computing the majority on every input with a constant probabilit y takes $\\Omega(\\log n)$ space. We extend our lower bound to proving tig ht lower bounds for solving multiple\, randomly interleaved copies of the coin problem\, as well as for solving the OR of multiple copies of a varia nt of the coin problem. Our proofs involve new measures of information com plexity that are well-suited for data streams.\n\nWe use these lower bound s to obtain a number of new results for data streams. In each case there i s an underlying $d$-dimensional vector x with additive updates to its coor dinates given in a stream of length $m$. The input streams arising from ou r coin lower bound have nice distributional properties\, and consequently for many problems for which we only had lower bounds in general turnstile streams\, we now obtain the same lower bounds in more natural models\, suc h as the bounded deletion model\, in which $\\|x\\|_2$ never drops by a co nstant fraction of what it was earlier\, or in the random order model\, in which the updates are ordered randomly.\n\nBased on joint work with Mark Braverman and David P. Woodruff.\n LOCATION:https://researchseminars.org/talk/TCSPlus/18/ END:VEVENT END:VCALENDAR