csci 3|6907 : randomized algorithms

Possible topics for student presentations

1. Load-Balancing: Talwar-Wieder [proceedings | full], Godfrey [proceedings]
2. Sublinear time algorithms: Chazelle-Rubinfeld-Trevisan [proceedings], Bogdanov-Obata-Trevisan [proceedings]
3. Spectral algorithms: Trevisan [full]
4. Hiring problem: Broder et. al [proceedings]
5. Constant-Time Approximation Algorithms: Nguyen-Onak [paper]
6. Streaming algorithms: Andoni-Krauthgamer-Onak [paper]
7. Satisfiability: Moser [paper]

• Apr 10: Mahesh (Spectral Algorithms) + Junyu (Satisfiability) + Mofan (Sublinear time algorithms)
• Apr 17: Mohammad (Constant-Time Approximation Algorithms) + Xuejing (Sublinear time algorithms) + Yang (Hiring problem)
• Apr 24: Jingxin (Balanced Allocations: the Weighted Case) + Jinho (Join-Idle-Queue)