E-Graphs as Circuits, and Optimal Extraction via Treewidth

Glenn Sun, Yihong Zhang, Haobin Ni

We demonstrate a new connection between e-graphs and Boolean circuits. This allows us to adapt existing literature on circuits to easily arrive at an algorithm for optimal e-graph…