Winter 2021: Succinct Graph Data Structures

From social networks to road maps to the internet, the modern world is dominated by data represented in enormously large graphs. An effective way to make sense of a massive graph is to create a much smaller one that is “similar” to the original in some critical ways. But how accurately can this be done? What methods of graph compression take on the least error? What structural properties of a network make it easy or hard to accurately express in small space? This class will develop the theoretical underpinnings of graph compression algorithms in a mathematically rigorous, proof-based way.