[Colloquium] TTIC Colloquium: Ping Li, Cornell University
Julia MacGlashan
macglashan at tti-c.org
Mon May 17 09:30:21 CDT 2010
*REMINDER*
When: *Monday, May 17 @ 1:00pm*
Where: * TTIC Conference Room #526*, 6045 S Kenwood Ave, 5th Floor
Who: * **Ping Li*, Cornell University
Title: * **Compressed Counting for Estimating Frequency
Moments and Entropy of Data Streams***
Estimating the p-th frequency moment of data stream is a very heavily
studied problem. The problem is actually trivial when p = 1, assuming the
strict Turnstile model. The sample complexity of our proposed algorithm is
essentially O(1) near p=1. This is a very large improvement over the
previously believed O(1/eps^2) bound. The proposed algorithm makes the
long-standing problem of entropy estimation an easy task.
Host: David McAllester, mcallester at ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100517/90070874/attachment.htm
More information about the Colloquium
mailing list