[Colloquium] TTIC Colloquium: Ping Li, Cornell University

[Julia MacGlashan]

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/20100513/799261ac/attachment.htm