Electrical Engineering and Computer Science
menu MENU

Winter 2021: Succinct Graph Data Structures

Winter 2021: Succinct Graph Data Structures

Course No:
EECS 598-003
Credit Hours:
3 credits
Instructor:
Gregory Bodwin
Prerequisites:
EECS 203 and EECS 281 and MATH 217 (or equivalent), grad standing, or permission of instructor

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.

Topics will include graph spanners and distance preservers (which compress graph distances), block models and regularity lemmas (which compress graph cuts), and spectral sparsiers (which compress graph spectra). Other topics may be set dynamically, based on active student interest and feedback.
More info (pdf)