Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Theoretical Computer Science

An improved algorithm for learning sparse parities in the presence of noise

Di Yan, Yu Yu, Hanlin Liu, Shuoyao Zhao, Jiang Zhang

Published Apr 30, 2021• 5 citations
Publisher
DOI
10.1016/j.tcs.2021.04.026

Related papers

On Noise-Tolerant Learning of Sparse Parities and Related Problems

Elena Grigorescu, Lev Reyzin, Santosh Vempala

Lecture notes in computer science•Jan 1, 2011•23 citations

Feature learning via mean-field Langevin dynamics: classifying sparse parities and beyond

Taiji Suzuki, Denny C.-Y. Wu, Kazusato Oko +1 more

neural information processing systems•Jan 1, 2023•0 citations

Solving the Learning Parity with Noise Problem Using Quantum Algorithms

Bénédikt Tran, Serge Vaudenay B

Lecture notes in computer science•Jan 1, 2022•1 citation

Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas

Gregory J. Valiant

Given a set of n d-dimensional Boolean vectors with the promise that the vectors are chosen uniformly at random with the exception of two vectors that have Pearson-correlation ρ (Hamming distance d · 1-ρ/2), how quickly can one find the two correlated vectors? We present an algorithm which, for any constants ε, ρ >; 0 and d >;>; logn/ρ2, finds the correlated pair with high probability, and runs in time O(n 3ω/4 + ϵ)1.8), where w2-O(ρ)), given by Paturi et al. [15], Locality Sensitive Hashing (LSH) [11] and the Bucketing Codes approach [6]. Applications and extensions of this basic algorithm yield improved algorithms for several other problems: ApproximateClosest Pair: For any sufficiently small constant ϵ >; 0, given n vectors in Rd, our algorithm returns a pair of vectors whose Euclidean distance differs from that of the closest pair by a factor of at most 1+ϵ, and runs in time O(n2-Θ(√ϵ)). The best previous algorithms (including LSH) have runtime O(n2-O(ϵ)). Learning Sparse Parity with Noise: Given samples from an instance of the learning parity with noise problem where each example has length n, the true parity set has size at most kkpoly(1/1-2η)0.8kpoly(1/1-2η). This is the first algorithm with no depenJence on η in the exponent of n, aside from the trivial brute-force algorithm. Learning k-Juntas with Noise: Given uniformly random length n Boolean vectors, together with a label, which is some function of just kkpoly(1/1-2η)0.8kpoly(1/1-2η), 2 which improves on the previous best of >; nk(1-2/2k)poly( 1/1-2η ), from [8]. Learning k-Juntas without Noise:1 Our results for learning sparse parities with noise imply an algorithm for learning juntas without noise with runtime n ω+ϵ/4kpoly(n)0.6kpoly(n), which improves on the runtime n ω+1/ω poly(n) ≈ n0.7kpoly(n) of Mossel n et al. [13].

Annual Symposium on Foundations of Computer Science•Oct 1, 2012•69 citations

On learning k-parities with and without noise

Arnab Bhattacharyya, Gadekar, Ameet, Ninad Rajgopal

We first consider the problem of learning $k$-parities in the on-line mistake-bound model: given a hidden vector $x \in \{0,1\}^n$ with $|x|=k$ and a sequence of "questions" $a_1, a_2, ...\in \{0,1\}^n$, where the algorithm must reply to each question with $< a_i, x> \pmod 2$, what is the best tradeoff between the number of mistakes made by the algorithm and its time complexity? We improve the previous best result of Buhrman et al. by an $\exp(k)$ factor in the time complexity. Second, we consider the problem of learning $k$-parities in the presence of classification noise of rate $η\in (0,1/2)$. A polynomial time algorithm for this problem (when $η> 0$ and $k = ω(1)$) is a longstanding challenge in learning theory. Grigorescu et al. showed an algorithm running in time ${n \choose k/2}^{1 + 4η^2 +o(1)}$. Note that this algorithm inherently requires time ${n \choose k/2}$ even when the noise rate $η$ is polynomially small. We observe that for sufficiently small noise rate, it is possible to break the $n \choose k/2$ barrier. In particular, if for some function $f(n) = ω(1)$ and $α\in [1/2, 1)$, $k = n/f(n)$ and $η= o(f(n)^{- α}/\log n)$, then there is an algorithm for the problem with running time $poly(n)\cdot {n \choose k}^{1-α} \cdot e^{-k/4.01}$.

arXiv:1502.05375•Feb 18, 2015•4 citations

Improved learning of k-parities

Arnab Bhattacharyya, Ameet Gadekar, Ninad Rajgopal

Theoretical Computer Science•Aug 27, 2020•2 citations
Given a set of n d-dimensional Boolean vectors with the promise that the vectors are chosen uniformly at random with the exception of two vectors that have Pearson-correlation ρ (Hamming distance d · 1-ρ/2), how quickly can one find the two correlated vectors? We present an algorithm which, for any constants ε, ρ >; 0 and d >;>; logn/ρ2, finds the correlated pair with high probability, and runs in time O(n 3ω/4 + ϵ)1.8), where w2-O(ρ)), given by Paturi et al. [15], Locality Sensitive Hashing (LSH) [11] and the Bucketing Codes approach [6]. Applications and extensions of this basic algorithm yield improved algorithms for several other problems: ApproximateClosest Pair: For any sufficiently small constant ϵ >; 0, given n vectors in Rd, our algorithm returns a pair of vectors whose Euclidean distance differs from that of the closest pair by a factor of at most 1+ϵ, and runs in time O(n2-Θ(√ϵ)). The best previous algorithms (including LSH) have runtime O(n2-O(ϵ)). Learning Sparse Parity with Noise: Given samples from an instance of the learning parity with noise problem where each example has length n, the true parity set has size at most kkpoly(1/1-2η)0.8kpoly(1/1-2η). This is the first algorithm with no depenJence on η in the exponent of n, aside from the trivial brute-force algorithm. Learning k-Juntas with Noise: Given uniformly random length n Boolean vectors, together with a label, which is some function of just kkpoly(1/1-2η)0.8kpoly(1/1-2η), 2 which improves on the previous best of >; nk(1-2/2k)poly( 1/1-2η ), from [8]. Learning k-Juntas without Noise:1 Our results for learning sparse parities with noise imply an algorithm for learning juntas without noise with runtime n ω+ϵ/4kpoly(n)0.6kpoly(n), which improves on the runtime n ω+1/ω poly(n) ≈ n0.7kpoly(n) of Mossel n et al. [13].
We first consider the problem of learning kkk-parities in the on-line mistake-bound model: given a hidden vector x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n with ∣x∣=k|x|=k∣x∣=k and a sequence of "questions" a1,a2,...∈{0,1}na_1, a_2, ...\in \{0,1\}^na1​,a2​,...∈{0,1}n, where the algorithm must reply to each question with <ai,x>(mod2)< a_i, x> \pmod 2<ai​,x>(mod2), what is the best tradeoff between the number of mistakes made by the algorithm and its time complexity? We improve the previous best result of Buhrman et al. by an exp⁡(k)\exp(k)exp(k) factor in the time complexity. Second, we consider the problem of learning kkk-parities in the presence of classification noise of rate η∈(0,1/2)η\in (0,1/2)η∈(0,1/2). A polynomial time algorithm for this problem (when η>0η> 0η>0 and k=ω(1)k = ω(1)k=ω(1)) is a longstanding challenge in learning theory. Grigorescu et al. showed an algorithm running in time (nk/2)1+4η2+o(1){n \choose k/2}^{1 + 4η^2 +o(1)}(k/2n​)1+4η2+o(1). Note that this algorithm inherently requires time (nk/2){n \choose k/2}(k/2n​) even when the noise rate ηηη is polynomially small. We observe that for sufficiently small noise rate, it is possible to break the (nk/2)n \choose k/2(k/2n​) barrier. In particular, if for some function f(n)=ω(1)f(n) = ω(1)f(n)=ω(1) and α∈[1/2,1)α\in [1/2, 1)α∈[1/2,1), k=n/f(n)k = n/f(n)k=n/f(n) and η=o(f(n)−α/log⁡n)η= o(f(n)^{- α}/\log n)η=o(f(n)−α/logn), then there is an algorithm for the problem with running time poly(n)⋅(nk)1−α⋅e−k/4.01poly(n)\cdot {n \choose k}^{1-α} \cdot e^{-k/4.01}poly(n)⋅(kn​)1−α⋅e−k/4.01.