12 Pages
English
Gain access to the library to view online
Learn more

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

-

Gain access to the library to view online
Learn more
12 Pages
English

Description

The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem ? (Extended Abstract) Vadim Lyubashevsky University of California at San Diego, La Jolla CA 92093, USA Abstract. In [2], Blum et al. demonstrated the first sub-exponential algorithm for learning the parity function in the presence of noise. They solved the length-n parity problem in time 2O(n/ logn) but it required the availability of 2O(n/ logn) labeled examples. As an open problem, they asked whether there exists a 2o(n) algorithm for the length-n parity problem that uses only poly(n) labeled examples. In this work, we provide a positive answer to this question. We show that there is an algorithm that solves the length-n parity problem in time 2O(n/ log logn) using n1+ labeled examples. This result immediately gives us a sub-exponential algorithm for decoding n ? n1+ random binary linear codes (i.e. codes where the messages are n bits and the codewords are n1+ bits) in the presence of random noise. We are also able to extend the same techniques to provide a sub-exponential algorithm for dense instances of the random subset sum problem.

  • sum problem

  • distribution over

  • given n1

  • binary linear

  • high density

  • random binary

  • sub-section

  • exponential algorithm

  • random subset


Subjects

Informations

Published by
Reads 11
Language English

Exrait

TheParityProbleminthePresenceofNoise,DecodingRandomLinearCodes,andtheSubsetSumProblem?(ExtendedAbstract)VadimLyubashevskyUniversityofCaliforniaatSanDiego,LaJollaCA92093,USAvlyubash@cs.ucsd.eduAbstract.In[2],Blumetal.demonstratedthefirstsub-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}n1andliequalscai(mod2)withprobability2+ηand1cai(mod2)withprob-ability21η.Theproblemistorecoverc.In[2],Blum,Kalai,andWassermandemonstratedthefirstsub-exponentialalgorithmforsolvingthisproblem.Theygaveanalgorithmthatrecoverscintime2O(n/logn)using2O(n/logn)labeledδexamplesforvaluesofηisgreaterthan2nforanyconstantδ<1.Anopenproblemwaswhetheritwaspossibletohaveanalgorithmwithasub-exponentialrunningtimewhenonlygivenaccesstoapolynomialnumberoflabeledexam-ples.Inthiswork,weshowthatbyhavingaccesstoonlyn1+labeledexamples,δwecanrecovercintime2O(n/loglogn)forvaluesofηgreaterthan2(logn).Sothepenaltywepayforusingfewerexamplesisbothinthetimeandtheerrortolerance.?ResearchsupportedinpartbyNSFgrantCCR-0093029