# On Exact Learning of d-Monotone Functions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 18 references that are in the map.
- First posted on arXiv 3 Feb 2025.

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

- [Properly learning monotone functions via local reconstruction](https://mlsanity.com/paper/2204.11894/) (2022)
- [Learning circuits with few negations](https://mlsanity.com/paper/1410.8420/) (2014)
- [Downsampling for Testing and Learning in Product Distributions](https://mlsanity.com/paper/2007.07449/) (2020)
- [Agnostic proper learning of monotone functions: beyond the black-box correction barrier](https://mlsanity.com/paper/2304.02700/) (2023)
- [Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions](https://mlsanity.com/paper/2310.12375/) (2023)

## Built on by (most cited first, 1 of 1)

- [Optimal Quantum-Classical Separations for Exact Learning](https://mlsanity.com/paper/2609.38073/) (2026)

## Abstract (arXiv)

In this paper, we study the learnability of the Boolean class of d-monotone functions f:cal X→0,1 from membership and equivalence queries, where (cal X,≤) is a finite lattice. We show that the class of d-monotone functions that are represented in the form f=F(g1,g2,ldots,gd), where F is any Boolean function F:0,1d→0,1 and g1,ldots,gd:cal X→ 0,1 are any monotone functions, is learnable in time σ(cal X)· (size(f)/d+1)d where σ(cal X) is the maximum sum of the number of immediate predecessors in a chain from the largest element to the smallest element in the lattice cal X and size(f)=size(g1)+cdots+size(gd), where size(gi) is the number of minimal elements in gi-1(1). For the Boolean function f:0,1n→0,1, the class of d-monotone functions that are represented in the form f=F(g1,g2,ldots,gd), where F is any Boolean function and g1,ldots,gd are any monotone DNF, is learnable in time O(n2)· (size(f)/d+1)d where size(f)=size(g1)+cdots+size(gd). In particular, this class is learnable in polynomial time when d is constant. Additionally, this class is learnable in polynomial time when size(gi) is constant for all i and d=O(log n).