# Learning with distributional inverters

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 31 references that are in the map.
- First posted on arXiv 23 Dec 2021.

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

- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness](https://mlsanity.com/paper/1611.01190/) (2016)

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

- [Samplability makes learning easier](https://mlsanity.com/paper/2512.01276/) (2025)

## Abstract (arXiv)

We generalize the "indirect learning" technique of Furst et. al., 1991 to reduce from learning a concept class over a samplable distribution μ to learning the same concept class over the uniform distribution. The reduction succeeds when the sampler for μ is both contained in the target concept class and efficiently invertible in the sense of Impagliazzo & Luby, 1989. We give two applications. - We show that AC0[q] is learnable over any succinctly-described product distribution. AC0[q] is the class of constant-depth Boolean circuits of polynomial size with AND, OR, NOT, and counting modulo q gates of unbounded fanins. Our algorithm runs in randomized quasi-polynomial time and uses membership queries. - If there is a strongly useful natural property in the sense of Razborov & Rudich 1997 -- an efficient algorithm that can distinguish between random strings and strings of non-trivial circuit complexity -- then general polynomial-sized Boolean circuits are learnable over any efficiently samplable distribution in randomized polynomial time, given membership queries to the target function