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

Applications of e-graphs to program synthesis have recently seen a rise in popularity. The efficient equality saturation workload that they enable makes them an ideal tool for program search and optimization. Unfortunately, straightforward approaches to dealing with beta-reduction in a complete manner cause equality saturation to be overrun with additional terms, making the process slow and often intractable. Yet some of us would still like to have complete (or close to complete) beta-reduction in the languages on which we perform equality saturation. We give an overview of approaches to dealing with beta-reduction and propose a fast and simple method that keeps the e-graph size down by culling unnecessary terms.

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