mlsanityData to 7 Oct 2026

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

arXiv 2109.10162 ↗First posted 21 Sep 2021cs.LG math.FA stat.MLcited by 8

Not on the map. Why?

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.

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

Builds on

0 of 16 references.

No references here yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 1; 2024: 3; 2025: 0; 2026: 2.

8 papers.

  1. 2022Learning to predict arbitrary quantum processescited by 34
  2. 2023Classical Verification of Quantum Learningcited by 6
  3. 2022Low-degree learning and the metric entropy of polynomialscited by 3
  4. 2024Simple algorithms to test and learn local Hamiltonianscited by 2
  5. 2024Learning low-degree quantum objectscited by 2
  6. 2024Predicting quantum channels over general product distributionscited by 2
  7. 2026Tight L_∞ Sample Complexity for Low-Degree and Sparse Boolean Polynomialscited by 0
  8. 2026Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cubecited by 0