E-graph Extraction Using ZDDs
Extraction on e-graphs is a fundamental operation when performing equality saturation. This talk proposal outlines how to use Zero-Suppressed Binary Decision Diagrams (ZDDs) for e-graph extraction. ZDDs provide a means of efficiently encoding large sets whose elements share common structure, and they can precisely encode all possible extractions for an e-graph. With such a ZDD, computing the optimal extraction is efficient. However, constructing the ZDD may take exponential time in the size of the e-graph. We show how to trade off ZDD size for optimality, yielding a practical extraction technique that can outperform the greedy algorithm. This is work in progress: in particular, we need further evaluation against other extraction algorithms, and against a wider set of examples.
Sun 18 JunDisplayed time zone: Eastern Time (US & Canada) change
16:00 - 17:50 | |||
16:00 20mTalk | Optimizing Beta-Reduction in E-Graphs EGRAPHS Emmanuel Anaya Gonzalez UCSD, Cole Kurashige UCSD, Aditya Giridharan UCSD, Nadia Polikarpova University of California at San Diego File Attached | ||
16:20 20mTalk | Improving Term Extraction with Acyclic Constraints EGRAPHS Deyuan (Mike) He Princeton University, Haichen Dong Princeton University, Sharad Malik Princeton University, Aarti Gupta Princeton University File Attached | ||
16:40 20mTalk | E-graph Extraction Using ZDDs EGRAPHS Eli Rosenthal Google |