# Learning low-degree functions from a logarithmic number of random queries

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 16 references that are in the map.
- First posted on arXiv 21 Sep 2021.

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

- [Learning to predict arbitrary quantum processes](https://mlsanity.com/paper/2210.14894/) (2022)
- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [Low-degree learning and the metric entropy of polynomials](https://mlsanity.com/paper/2203.09659/) (2022)
- [Simple algorithms to test and learn local Hamiltonians](https://mlsanity.com/paper/2404.06282/) (2024)
- [Learning low-degree quantum objects](https://mlsanity.com/paper/2405.10933/) (2024)
- [Predicting quantum channels over general product distributions](https://mlsanity.com/paper/2409.03684/) (2024)
- [Tight L_∞ Sample Complexity for Low-Degree and Sparse Boolean Polynomials](https://mlsanity.com/paper/2606.17319/) (2026)
- [Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube](https://mlsanity.com/paper/2610.12358/) (2026)

## Abstract (arXiv)

We prove that every bounded function f:-1,1n→[-1,1] of degree at most d can be learned with L2-accuracy varepsilon and confidence 1-δ from log(tfracnδ),varepsilon-d-1 C^d3/2√log d random queries, where C>1 is a universal finite constant.