BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/730
DTSTAMP:20230914T125936Z
SUMMARY:Strong Fooling Sets for Multi-Player Communication with Application
 s to Deterministic Estimation of Stream Statistics
DESCRIPTION:Speaker: Sagar Kale (Dartmouth College\nDepartment of Computer 
 Science\n6211 Sudikoff Lab\nHanover\, NH-03755-3510\nUnited States of Amer
 ica)\n\nAbstract: \nWe develop a paradigm for studying multi-player determ
 inistic communication\, based on a novel combinatorial concept that we cal
 l a {\\em strong fooling set}. Our paradigm leads to optimal lower bounds 
 on the per-player communication required for solving multi-player EQUALITY
  problems in a private-message setting. This in turn gives a very strong--
 -$O(1)$ versus $\\Omega(n)$---separation between private-message and one-w
 ay blackboard communication complexities.\n\nApplying our communication co
 mplexity results\, we show that for deterministic data streaming algorithm
 s\, even loose estimations of some basic statistics of an input stream req
 uire large amounts of space. For instance\, approximating the frequency mo
 ment $F_k$ within a factor $\\alpha$ requires $\\Omega(n/\\alpha^{1/(1-k)}
 )$ space for $k < 1$ and roughly $\\Omega(n/\\alpha^{k/(k-1)})$ space for 
 $k > 1$. In particular\, approximation within any {\\em constant} factor $
 \\alpha$\, however large\, requires {\\em linear space\, with the trivial 
 exception of $k = 1$. This is in sharp contrast to the situation for rando
 mized streaming algorithms\, which can approximate $F_k$ to within $(1\\pm
 \\varepsilon)$ factors using $\\widetilde{O}(1)$ space for $k \\le 2$ and 
 $o(n)$ space for all finite $k$ and all constant $\\varepsilon > 0$.  Pre
 vious linear-space lower bounds for deterministic estimation were limited 
 to small factors $\\alpha$\, such as $\\alpha < 2$ for approximating $F_0$
  or $F_2$.\n\nWe also provide certain space/approximation tradeoffs in a d
 eterministic setting for the problems of estimating the empirical entropy 
 of a stream as well as the size of the maximum matching and the edge conne
 ctivity of a streamed graph (this is joint work with Amit Chakrabarti).\n
URL:https://www.tcs.tifr.res.in/web/events/730
DTSTART;TZID=Asia/Kolkata:20161206T160000
DTEND;TZID=Asia/Kolkata:20161206T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR