# Approximating the Number of Relevant Variables in a Parity Implies Proper Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 41 references that are in the map.
- First posted on arXiv 16 Jul 2024.

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

- [On Lattices, Learning with Errors, Random Linear Codes, and Cryptography](https://mlsanity.com/paper/2401.03703/) (2024)
- [Exact Learning from an Honest Teacher That Answers Membership Queries](https://mlsanity.com/paper/1706.03935/) (2017)
- [On learning k-parities with and without noise](https://mlsanity.com/paper/1502.05375/) (2015)
- [On the hardness of learning sparse parities](https://mlsanity.com/paper/1511.08270/) (2015)

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

- [Fitting and Learning Basis-Restricted Propositional Formulas](https://mlsanity.com/paper/2609.08961/) (2026)

## Abstract (arXiv)

Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities. More specifically, let γ:mathbb R^+→ mathbb R^+, where γ(x) ≥ x, be any strictly increasing function. In our first result, we show that from any polynomial-time algorithm that returns a γ-approximation, D (i.e., γ-1(d(f)) ≤ D ≤ γ(d(f))), of the number of relevant variables~d(f) for any parity f, we can, in polynomial time, construct a solution to the long-standing open problem of polynomial-time learning k(n)-sparse parities (parities with k(n)≤ n relevant variables), where k(n) = ωn(1). In our second result, we show that from any T(n)-time algorithm that, for any parity f, returns a γ-approximation of the number of relevant variables d(f) of f, we can, in polynomial time, construct a poly(Gamma(n))T(Gamma(n)2)-time algorithm that properly learns parities, where Gamma(x)=γ(γ(x)). If T(Gamma(n)2)=exp(o(n/log n)), this would resolve another long-standing open problem of properly learning parities in the presence of random classification noise in time exp(o(n/log n)).