Pith. sign in

REVIEW 4 cited by

E-Graphs as Circuits, and Optimal Extraction via Treewidth

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2408.17042 v2 pith:UJW6QMGB submitted 2024-08-30 cs.DS

Glenn Sun , Yihong Zhang , Haobin Ni This is my paper
classification cs.DS
keywords e-graphscircuitstreewidthe-graphalgorithmallowscircuitextraction
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

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.

Discussion (0). Sign in to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Rewrite System Showdown: Stochastic Search vs. EqSat

    cs.PL 2026-05 unverdicted novelty 7.0 of 10

    The paper benchmarks equality saturation against stochastic search on five program optimization tasks to evaluate the effectiveness of e-graphs.

  2. E-Graphs as a Persistent Compiler Abstraction

    cs.PL 2026-02 conditional novelty 7.0 of 10

    E-graphs become first-class compiler IR via the eqsat dialect, enabling persistent equality saturation; a partial Herbie reimplementation matches accuracy but is ~400× slower.

  3. Answer Set Programming for Egg Extraction and More

    cs.PL 2026-06 unverdicted novelty 6.0 of 10

    Answer set programming encodings for e-graph extraction match ILP efficiency on benchmarks and recover additional optimal solutions on complex instances.

  4. Rewrite System Showdown: Stochastic Search vs. EqSat

    cs.PL 2026-05 unverdicted novelty 6.0 of 10

    Empirical comparison of equality saturation versus stochastic search on five benchmarks to evaluate if e-graphs are superior for rewrite-based optimization.

Pith tools