Sublinear Algorithms

Default Time: Friday 2:30pm
Default Place: GHC 9115
Email me at konak@cs.cmu.edu if you want to be on the mailing list

Lectures

• Jan 27: Simple Examples
• Feb 3: Streaming Moments
• Feb 10: Estimating the Number of Distinct Elements. Lower Bounds via Communication Complexity.
• Feb 17: Streaming Algorithms for the Longest Increasing Subsequence Length and the Median
• Feb 24: Heavy Hitters and the Count-Min Sketch
• Mar 2: Distributed Functional Monitoring
• Mar 9: Estimating the F_k Moment for k>2
• Mar 16: Spring break
• Mar 23: Testing Uniformity
• Mar 30: Other Distribution Testing Examples
• Apr 4: Sublinear-Time Algorithms for Diameter and Minimum Spanning Tree Weight

Useful Links

• Recent List of Open Problems
• Property Testing: Current Research and Surveys
• Data Streams: Algorithms and Applications