Beyond Worst Case Analysis has Started!

September 18, 2018 • Antares Chen

The fall 2018 UGTCS Beyond Worst Case Analysis reading group is now in full swing!

In this week’s meeting, we discussed how the expected max clique size in a random \(\mathcal{G}_{n,p}\) graph is close to \(2\log(n)\)with high probability.

BWCA is a reading group that analyzes where worst-case analysis fails and provides more refined methods for analysis of algorithms. We cover topics such as average-case analysis for random instances, analysis of distributions with planted solutions, semi-random models, instance stability, and analysis of online algorithms.

We meet every week Monday 5:30 - 7:00pm and occasionally hold special group events to work on topic related exercises and programming tasks. If you’re interested, please check out the BWCA home page for more information. Next week we will be discussing the AKS algorithm for finding a planted clique of size \(\sqrt{n}\) in a random \(\mathcal{G}_{n,1/2}\) graph. We hope to see you there!