CS5330: Randomized Algorithms, Spring 2020.

Selected Highlights

• On the constructive Lovasz Local Lemma: Tan Likai, Wang Zhijian and Ryan Chew take us through Moser's constructive version of the LLL and conduct experiments to investigate how the algorithm performs when the assumptions are made weaker.


• A survey on k-means initialization methods: Huang Xiangyuan, Liu Siyuan, Wang Hao tell us about k-means++ and k-means||. They also suggest their own variant and perform experiments to compare the performance of the different algorithms.


• Randomized Decision Trees: Kiran Gopinathan and Jishnu Mohan give a comprehensive survey of recent advances in separations between deterministic and randomized complexity in the decision tree computational model. They also offer their thoughts on separating zero-error randomized and deterministic decision tree complexity.


• Discrepancy Theory: Shawn Lim surveys Lovett and Meka's constructive discrepancy minimization algorithm as well as Rothvoss's more general result for convex sets.