The Parity Problem in the Presence of Noise Decoding Random Linear Codes and the Subset

pages

English

Documents

Écrit par
Vadim Lyubashevsky

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

pages

English

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

English

sum problem

distribution over

given n1

binary linear

high density

random binary

sub-section

exponential algorithm

random subset

Voir

Publié par

pefav

Langue

English

High density storage media Time complexity

TheParityProbleminthePresenceofNoise,DecodingRandomLinearCodes,andtheSubsetSumProblem?(ExtendedAbstract)VadimLyubashevskyUniversityofCaliforniaatSanDiego,LaJollaCA92093,USAvlyubash@cs.ucsd.eduAbstract.In[2],Blumetal.demonstratedtheﬁrstsub-exponentialalgorithmforlearningtheparityfunctioninthepresenceofnoise.Theysolvedthelength-nparityproblemintime2O(n/logn)butitrequiredtheavailabilityof2O(n/logn)labeledexamples.Asanopenproblem,theyaskedwhetherthereexistsa2o(n)algorithmforthelength-nparityproblemthatusesonlypoly(n)labeledexamples.Inthiswork,weprovideapositiveanswertothisquestion.Weshowthatthereisanalgorithmthatsolvesthelength-nparityproblemintime2O(n/loglogn)usingn1+labeledexamples.Thisresultimmediatelygivesusasub-exponentialalgorithmfordecodingn×n1+randombinarylinearcodes(i.e.codeswherethemessagesarenbitsandthecodewordsaren1+bits)inthepresenceofrandomnoise.Wearealsoabletoextendthesametechniquestoprovideasub-exponentialalgorithmfordenseinstancesoftherandomsubsetsumproblem.1IntroductionInthelength-nparityproblemwithnoise,thereisanunknowntousvectorc∈{0,1}nthatwearetryingtolearn.Wearealsogivenaccesstoanoraclethatgeneratesexamplesaiandlabelsliwhereaiisuniformlydistributedin{0,1}n1andliequalsc∙ai(mod2)withprobability2+ηand1−c∙ai(mod2)withprob-ability21−η.Theproblemistorecoverc.In[2],Blum,Kalai,andWassermandemonstratedtheﬁrstsub-exponentialalgorithmforsolvingthisproblem.Theygaveanalgorithmthatrecoverscintime2O(n/logn)using2O(n/logn)labeledδexamplesforvaluesofηisgreaterthan2−nforanyconstantδ<1.Anopenproblemwaswhetheritwaspossibletohaveanalgorithmwithasub-exponentialrunningtimewhenonlygivenaccesstoapolynomialnumberoflabeledexam-ples.Inthiswork,weshowthatbyhavingaccesstoonlyn1+labeledexamples,δwecanrecovercintime2O(n/loglogn)forvaluesofηgreaterthan2−(logn).Sothepenaltywepayforusingfewerexamplesisbothinthetimeandtheerrortolerance.?ResearchsupportedinpartbyNSFgrantCCR-0093029

Voir