Vidéo pédagogique

3.9. Generalized Birthday Algorithm for Decoding

Réalisation : 5 mai 2015 Mise en ligne : 5 mai 2015
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3

The session nine isdevoted to the application of the Generalized BirthdayAlgorithm to decoding. The Generalized BirthdayAlgorithm was presented by David Wagner in 2002, in amore general context. In fact, at order a,the Generalized Birthday Algorithm solves thefollowing problem: we are given 2^a lists of vectors of size L and we want to find xi, one in every list Li,such that the sum of all the xi is 0. If the lists Li are large enough,then the algorithm runs in time 2^(l/(a+1)). Note that the case a=1 corresponds to the usual birthday paradox. This Generalized BirthdayAlgorithm can be applied to solve the problem of decoding. In practice, it willapply mostly to instances of Computational SyndromeDecoding which have many solutions and, more than that,it aims at finding one solution only amongthose many solutions. I would revisit theBirthday Decoding again but this time I will changeslightly the context. So now I would assume thatthere are many solutions. I will be more specificabout how many solutions are needed when I amdone with this slide. And among those manysolutions, I only want to find one. So, I will build the listsexactly in the same manner as before. Here, I write s = s1 + s2 where I cut the targetsyndrome s arbitrarily. There is no specific reasonto do that except to have a nice symmetry and it willbe useful for higher order Generalized Birthday Algorithm. So, I have those two listsand I am interested by any element in the intersection. But since I only want onesolution to my problem, I am only interested to have oneelement in the intersection. So, I only want theintersection whose size is L²/2^(n-k) where L is the size ofboth lists L1 and L2. I am interested that thissize is larger than one. This will be the case ifI choose L = 2^((n-k)/2).And in that case my listsare large enough to have a non-empty intersection, andthe workfactor to obtain a non-empty intersectionis L that is 2^((n-k)/2). Once this is set, itgives me the limit for the size list. I need alist of size 2^((n-k)/2) and I also know fromthe way the lists are constructed that Lcannot exceed (n/2,w/2). So, I need the condition here in red in order to be able to apply this version of Birthday Decoding. Now, I can define aGeneralized Birthday Algorithm of order 2 for decoding. So, I do exactly the samething as before except that I split everything infour parts instead of two.

Date de réalisation
Langue :
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
Citer cette ressource:
Inria. (2015, 5 mai). 3.9. Generalized Birthday Algorithm for Decoding. [Vidéo]. Canal-U. (Consultée le 24 janvier 2022)

Dans la même collection

Avec les mêmes intervenants

Sur le même thème

  • Topological insights in neuroscience
    Topological insights in neuroscience
    Hess Bellwald

    Over the past decade, and particularly over the past five years, research at the interface of topology and neuroscience has grown remarkably fast. Topology has, for example, been successfully applied

  • Modélisation de la croissance des micro-organismes
    Modélisation de la croissance des micro-organismes
    Hidde de

    La croissance microbienne peut être formulée comme un problème d'optimisation : comment allouer les ressources nutritives extraites de l'environnement aux différentes fonctions cellulaires afin de

  • Caches, montrez-vous !
    Caches, montrez-vous !

    Les processeurs actuels permettent de l'ordre de quelques tera-opérations par seconde. Puissance nécessaire pour soutenir les besoins en simulation numérique, qui constitue, après la théorie et l

  • Théorie de l’appariement et applications actuelles
    Théorie de l’appariement et applications actuelles

    Pourquoi y a-t-il tant de personnes sans emploi alors qu’au même moment un grand nombre de postes sont disponibles ? La théorie de l’appariement analyse ces problèmes où un certain nombre de

  • Self-Supervised Visual Learning and Synthesis
    Self-Supervised Visual Learning and Synthesis
    Alexei A.

    Computer vision has made impressive gains through the use of deep learning models, trained with large-scale labeled data. However, labels require expertise and curation and are expensive to collect.

  • Theoretical Foundations for Runtime Monitoring
    Theoretical Foundations for Runtime Monitoring

    Runtime monitoring/verification is a lightweight technique that complements other verification methods in a multi-pronged approach towards ensuring software correctness. The technique poses novel

  • CoNeCo: Concurrency, Networks and Coinduction
    CoNeCo: Concurrency, Networks and Coinduction

    In recent years, concurrent Kleene algebra (CKA), an extension of Kleene Algebra (KA) that includes concurrent composition as a first-class citizen, has been proposed by Hoare et al. as a setting to

  • Le numérique face aux enjeux environnementaux et sociétaux
    Le numérique face aux enjeux environnementaux et sociétaux

    L’humanité est aujourd'hui confrontée à des défis sans précédent et étroitement entremêlés. Le risque d'effondrement environnemental et civilisationnel est désormais établi. Face à ces enjeux, de