1 citations · 2 across the 11 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.CC2015
On the hardness of learning sparse parities
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal +1
This work investigates the hardness of computing sparse solutions to systems of linear equations over F_2. Consider the k-EvenSet problem: given a homogeneous system of linear equa…
cs.DS2015
On learning k-parities with and without noise
Arnab Bhattacharyya, Ameet Gadekar, Ninad Rajgopal
We first consider the problem of learning -parities in the on-line mistake-bound model: given a hidden vector with and a sequence of "questions" $a_1,…