Parameterized Complexity of Running an E-Graph
E-Graphs are a data structures that allow us to represent many equivalent programs at once. This post won’t get into background on e-graphs, so check out previous blog posts or the original egg talk. A variety of research projects at PLSE use e-graphs because they are a powerful and flexible tool for performing program optimization. Unfortunately, e-graphs suffer from a serious problem: their run-time performance is unpredictable.