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

Vadim Lyubashevsky

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

Sujets

• High density storage media
• Time complexity

Informations

• Publié par: pefav
• Nombre de lectures: 11
• Langue: English

Extrait

TheParityProbleminthePresenceofNoise, DecodingRandomLinearCodes,andtheSubset SumProblem ? (ExtendedAbstract) VadimLyubashevsky UniversityofCaliforniaatSanDiego,LaJollaCA92093,USA [e-mail] Abstract.In[2],Blumetal.demonstratedthefirstsub-exponential algorithmforlearningtheparityfunctioninthepresenceofnoise.They solvedthelength-nparityproblemintime2 O(n/logn) butitrequired theavailabilityof2 O(n/logn) labeledexamples.Asanopenproblem, theyaskedwhetherthereexistsa2 o(n) algorithmforthelength-nparity problemthatusesonlypoly(n)labeledexamples.Inthiswork,weprovide apositiveanswertothisquestion.Weshowthatthereisanalgorithm thatsolvesthelength-nparityproblemintime2 O(n/loglogn) usingn 1+ labeledexamples.Thisresultimmediatelygivesusasub-exponential algorithmfordecodingn × n 1+ randombinarylinearcodes(i.e.codes wherethemessagesarenbitsandthecodewordsaren 1+ bits)inthe presenceofrandomnoise.Wearealsoabletoextendthesametechniques toprovideasub-exponentialalgorithmfordenseinstancesoftherandom subsetsumproblem. 1Introduction Inthelength-nparityproblemwithnoise,thereisanunknowntousvector c ∈{ 0,1 } n thatwearetryingtolearn.Wearealsogivenaccesstoanoraclethat generatesexamplesa i andlabelsl i wherea i isuniformlydistributedin { 0,1 } n 1 andl i equalsc ∙ a i (mod2)withprobability 2 +ηand1 − c ∙ a i (mod2)withprob- ability 2 1 − η.Theproblemistorecoverc.In[2],Blum,Kalai,andWasserman demonstratedthefirstsub-exponentialalgorithmforsolvingthisproblem.They gaveanalgorithmthatrecoverscintime2 O(n/logn) using2 O(n/logn) labeled δ examplesforvaluesofηisgreaterthan2 −n foranyconstantδ<1.Anopen problemwaswhetheritwaspossibletohaveanalgorithmwithasub-exponential runningtimewhenonlygivenaccesstoapolynomialnumberoflabeledexam- ples.Inthiswork,weshowthatbyhavingaccesstoonlyn 1+ labeledexamples, δ wecanrecovercintime2 O(n/loglogn) forvaluesofηgreaterthan2 − (logn) .So thepenaltywepayforusingfewerexamplesisbothinthetimeandtheerror tolerance. ? ResearchsupportedinpartbyNSFgrantCCR-0093029