# Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- First posted on arXiv 14 Jan 2025.

## Abstract (arXiv)

The tree-width of a multivariate polynomial is the tree-width of the hypergraph with hyperedges corresponding to its terms. Multivariate polynomials of bounded tree-width have been studied by Makowsky and Meer as a new sparsity condition that allows for polynomial solvability of problems which are intractable in general. We consider a variation on this theme for Boolean variables. A representation of a Boolean function as the sign of a polynomial is called a polynomial threshold representation. We discuss Boolean functions representable as polynomial threshold functions of bounded tree-width and present two applications to Bayesian network classifiers, a probabilistic graphical model. Both applications are in Explainable Artificial Intelligence (XAI), the research area dealing with the black-box nature of many recent machine learning models. We also give a separation result between the representational power of positive and general polynomial threshold functions.