Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.17042 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917837058080768 |
|---|---|
| author | Sun, Glenn Zhang, Yihong Ni, Haobin |
| author_facet | Sun, Glenn Zhang, Yihong Ni, Haobin |
| contents | 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 extraction, parameterized by treewidth, which runs in $2^{O(w^2)}\text{poly}(w, n)$ time, where $w$ is the treewidth of the e-graph. Additionally, we show how the circuit view of e-graphs allows us to apply powerful simplification techniques, and we analyze a dataset of e-graphs to show that these techniques can reduce e-graph size and treewidth by 40-80% in many cases. While the core parameterized algorithm may be adapted to work directly on e-graphs, the primary value of the circuit view is in allowing the transfer of ideas from the well-established field of circuits to e-graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_17042 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | E-Graphs as Circuits, and Optimal Extraction via Treewidth Sun, Glenn Zhang, Yihong Ni, Haobin Data Structures and Algorithms 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 extraction, parameterized by treewidth, which runs in $2^{O(w^2)}\text{poly}(w, n)$ time, where $w$ is the treewidth of the e-graph. Additionally, we show how the circuit view of e-graphs allows us to apply powerful simplification techniques, and we analyze a dataset of e-graphs to show that these techniques can reduce e-graph size and treewidth by 40-80% in many cases. While the core parameterized algorithm may be adapted to work directly on e-graphs, the primary value of the circuit view is in allowing the transfer of ideas from the well-established field of circuits to e-graphs. |
| title | E-Graphs as Circuits, and Optimal Extraction via Treewidth |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.17042 |