Ouvrir le menu
Publier un document
Alternate Text
clear
fr
Ouvrir le menu
Category Category The Parity Problem in the Presence of Noise Decoding Random Linear Codes and the Subset

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

icon

12

pages

icon

English

icon

Documents

Écrit par

Publié par

Lire un extrait
Alternate Text
Lire un extrait
Alternate Text

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

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
icon

12

pages

icon

English

icon

Ebook

Lire un extrait
Alternate Text
Lire un extrait
Alternate Text

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

Publié par

Nombre de lectures

11

Langue

English

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


Voir Alternate Text

Publié par

Nombre de lectures

11

Langue

English

High density storage media Time complexity
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}n1andliequalsc∙ai(mod2)withprobability2+ηand1−c∙ai(mod2)withprob-ability21−η.Theproblemistorecoverc.In[2],Blum,Kalai,andWassermandemonstratedthefirstsub-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 Alternate Text
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents
Signaler un problème
playstore
appstore
facebook twitter instagram youtube

YouScribe

Le catalogue

Le service

Les conditions

© 2010-2024 YouScribe
Livre audio en ligne - Développement personnel Livre en ligne Tout le catalogue Tous les Intérêts
Alternate Text
Category

Book

Book

icon play
icon play Infos