Sun 18 Jun 2023 16:40 - 17:00 at Magnolia 18 - EGRAPHS: Binding & Extraction

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 Jun

Displayed time zone: Eastern Time (US & Canada) change

16:00 - 17:50
EGRAPHS: Binding & ExtractionEGRAPHS at Magnolia 18

#egraphs-sun-magnolia18 Discord icon small YouTube icon small

16:00
20m
Talk
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
20m
Talk
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
20m
Talk
E-graph Extraction Using ZDDs
EGRAPHS