# Learning circuits with few negations

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2014.

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

- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [The Probably Approximately Correct Learning Model in Computational Learning Theory](https://mlsanity.com/paper/2511.08791/) (2025)
- [On Exact Learning of d-Monotone Functions](https://mlsanity.com/paper/2502.01265/) (2025)
- [New Distinguishers for Negation-Limited Weak Pseudorandom Functions](https://mlsanity.com/paper/2203.12246/) (2022)

## Abstract (arXiv)

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and the class of all functions. We study this generalization of monotonicity from the vantage point of learning theory, giving near-matching upper and lower bounds on the uniform-distribution learnability of circuits in terms of the number of negations they contain. Our upper bounds are based on a new structural characterization of negation-limited circuits that extends a classical result of A. A. Markov. Our lower bounds, which employ Fourier-analytic tools from hardness amplification, give new results even for circuits with no negations (i.e. monotone functions).