BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//128.220.13.64//NONSGML kigkonsult.se iCalcreator 2.20//
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Johns Hopkins Algorithms and Complexity
X-WR-CALDESC:
X-FROM-URL:https://www.cs.jhu.edu/~mdinitz/theory
X-WR-TIMEZONE:America/New_York
BEGIN:VTIMEZONE
TZID:America/New_York
X-LIC-LOCATION:America/New_York
BEGIN:STANDARD
DTSTART:20231105T020000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20240310T020000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:ai1ec-358@www.cs.jhu.edu/~mdinitz/theory
DTSTAMP:20231203T110213Z
CATEGORIES:
CONTACT:
DESCRIPTION:Speaker: Samson Zhou\nAffiliation: Carnegie Mellon University\n
Title: Tight Bounds for Adversarially Robust Streams and Sliding Windows v
ia Difference Estimators\nAbstract:\nWe introduce difference estimators fo
r data stream computation\, which provide approximations to F(v)-F(u) for
frequency vectors v\,u and a given function F. We show how to use such est
imators to carefully trade error for memory in an iterative manner. The fu
nction F is generally non-linear\, and we give the first difference estima
tors for the frequency moments F_p for p between 0 and 2\, as well as for
integers p>2. Using these\, we resolve a number of central open questions
in adversarial robust streaming and sliding window models.\nFor both model
s\, we obtain algorithms for norm estimation whose dependence on epsilon i
s 1/epsilon^2\, which shows\, up to logarithmic factors\, that there is no
overhead over the standard insertion-only data stream model for these pro
blems.
DTSTART;TZID=America/New_York:20210414T120000
DTEND;TZID=America/New_York:20210414T130000
SEQUENCE:0
SUMMARY:[Theory Seminar] Samson Zhou
URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-samson-zhou
-3/
X-COST-TYPE:free
X-ALT-DESC;FMTTYPE=text/html:\\n\\n\\n\\n\\nSpeaker: Sams
on Zhou

\nAffiliation: Carnegie Mellon University

\nTitle: Tigh
t Bounds for Adversarially Robust Streams and Sliding Windows via Differen
ce Estimators

\nAbstract:

\nWe introduce *difference estimat
ors* for data stream computation\, which provide approximations to F(v
)-F(u) for frequency vectors v\,u and a given function F. We show how to u
se such estimators to carefully trade error for memory in an iterative man
ner. The function F is generally non-linear\, and we give the first differ
ence estimators for the frequency moments F_p for p between 0 and 2\, as w
ell as for integers p>2. Using these\, we resolve a number of central open
questions in adversarial robust streaming and sliding window models.

\nFor both models\, we obtain algorithms for norm estimation whose depe
ndence on epsilon is 1/epsilon^2\, which shows\, up to logarithmic factors
\, that there is no overhead over the standard insertion-only data stream
model for these problems.

\n
END:VEVENT
END:VCALENDAR