Improved learning of k-parities
Loading...
Access rights
openAccess
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
8
Series
Theoretical Computer Science, Volume 840, pp. 249-256
Abstract
We consider the problem of learning k-parities in the online mistake-bound model: given a hidden vector x∈{0,1}n where the hamming weight of x is k and a sequence of “questions” a1,a2,…∈{0,1}n, where the algorithm must reply to each question with 〈ai,x〉(mod2), what is the best trade-off between the number of mistakes made by the algorithm and its time complexity? We improve the previous best result of Buhrman et al. [3] by an exp(k) factor in the time complexity. Next, we consider the problem of learning k-parities in the PAC model in the presence of random classification noise of rate [Formula Presented]. Here, we observe that even in the presence of classification noise of non-trivial rate, it is possible to learn k-parities in time better than (nk/2), whereas the current best algorithm for learning noisy k-parities, due to Grigorescu et al. [9], inherently requires time (nk/2) even when the noise rate is polynomially small.Description
Other note
Citation
Bhattacharyya, A, Gadekar, A & Rajgopal, N 2020, 'Improved learning of k-parities', Theoretical Computer Science, vol. 840, pp. 249-256. https://doi.org/10.1016/j.tcs.2020.08.025