# Almost Optimal Testers for Concise Representations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2019.

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

- [On Learning and Testing Decision Tree](https://mlsanity.com/paper/2108.04587/) (2021)
- [Almost Optimal Proper Learning and Testing Polynomials](https://mlsanity.com/paper/2202.03207/) (2022)

## Abstract (arXiv)

We give improved and almost optimal testers for several classes of Boolean functions on n inputs that have concise representation in the uniform and distribution-free model. Classes, such as k-junta, k-linear functions, s-term DNF, s-term monotone DNF, r-DNF, decision list, r-decision list, size-s decision tree, size-s Boolean formula, size-s branching programs, s-sparse polynomials over the binary field and function with Fourier degree at most d. The method can be extended to several other classes of functions over any domain that can be approximated by functions that have a small number of relevant variables.