3 papers
cs.PL2026
Rewrite System Showdown: Stochastic Search vs. EqSat
Qiantan Hong, Rupanshu Soi, Yihong Zhang +1
Equality saturation has become a dominant paradigm for equational program optimization. However, it has never been rigorously compared to another approach to the same problem, even…
cs.PL2025
Semantic foundations of equality saturation
Dan Suciu, Yisu Remy Wang, Yihong Zhang
Equality saturation is an emerging technique for program and query optimization developed in the programming language community. It performs term rewriting over an E-graph, a data…
cs.DS2024
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…