# OPTDTALS: Approximate Logic Synthesis via Optimal Decision Trees Approach

arXiv: https://arxiv.org/abs/2408.12304 · HTML: https://mlsanity.com/paper/2408.12304/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 40 references that are in the map.
- First posted on arXiv 22 Aug 2024.

## Builds on (most cited first, 7 of 7)

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [k-way Hypergraph Partitioning via n-Level Recursive Bisection](https://mlsanity.com/paper/1511.03137/) (2015)
- [Optimizing Binary Decision Diagrams with MaxSAT for classification](https://mlsanity.com/paper/2203.11386/) (2022)
- [autoAx: An Automatic Design Space Exploration and Circuit Building Methodology utilizing Libraries of Approximate Components](https://mlsanity.com/paper/1902.10807/) (2019)
- [BLASYS: Approximate Logic Synthesis Using Boolean Matrix Factorization](https://mlsanity.com/paper/1805.06050/) (2018)

## Abstract (arXiv)

The growing interest in Explainable Artificial Intelligence (XAI) motivates promising studies of computing optimal Interpretable Machine Learning models, especially decision trees. Such models generally provide optimality in compact size or empirical accuracy. Recent works focus on improving efficiency due to the natural scalability issue. The application of such models to practical problems is quite limited. As an emerging problem in circuit design, Approximate Logic Synthesis (ALS) aims to reduce circuit complexity by sacrificing correctness. Recently, multiple heuristic machine learning methods have been applied in ALS, which learns approximated circuits from samples of input-output pairs. In this paper, we propose a new ALS methodology realizing the approximation via learning optimal decision trees in empirical accuracy. Compared to previous heuristic ALS methods, the guarantee of optimality achieves a more controllable trade-off between circuit complexity and accuracy. Experimental results show clear improvements in our methodology in the quality of approximated designs (circuit complexity and accuracy) compared to the state-of-the-art approaches.