Cut Tracing with E-Graphs for Boolean FHE Circuit Synthesis
summary
Proposes cut tracing that records replacement candidates from ESOP balancing and cut rewriting into an e-graph and then runs ILP-based extraction to jointly minimize multiplicative depth (MD) and multiplicative complexity (MC) for Boolean FHE circuits. Prototype flow yields up to 40% improvement in homomorphic evaluation time (about 10% on average) versus the greedy baseline, and improves ~30% over naïve equality saturation; extraction uses ILP-based extraction thanks to far fewer candidates but sometimes fails due to cycles.
AI-written summary · about
chapters (10)
- 0:00FHE and circuit optimization
- 1:23Boolean FHE circuits
- 3:10Limitations of cut-based methods
- 5:17Phase ordering problem
- 6:21Equality saturation limits
- 9:11Cut tracing with egraphs
- 11:39Evaluation vs baselines
- 13:44Comparison with equality saturation
- 14:24Conclusion and future work
- 15:35Q&A
related talks
20mFast and Optimal Extraction for Sparse Equality Graphs
22mAlgorithm-Aware Hardware Optimization using E-Graph Rewriting: how should we marry(…)
41mTalk by Elaine Shi (Carnegie Mellon University)
19mA Joint Approach to Instruction Scheduling and Algebraic Rewriting with E-Graphs
50mApplications of Obfuscation II
22mCircuit Optimization using Arithmetic Table Lookups
15mHEC: Equivalence Verification Checking for Code Transformation via Equality...
01h 01mCircularity Based IO, Part 1