Posts classified under: Amacc

The balance game is played on a graph G by two players, Admirable (A) and Impish (I), who take turns selecting unlabeled vertices of G, coloring them with their own color. The discrepancy in the balance game is defined as the difference of the number of well colored edges minus the number of monochromatic edges. The two players … Continue reading Séminaire Algorithmique : Paul Dorbec (GREYC) « How can the balance game be so unfair? »

Cryptography relies on building blocks called primitives used within constructions to build more complex algorithms.  The security of a scheme (i.e. of a construction instantiated with a primitive) is most often proven under some assumptions on the underlying primitive. However, security reductions only provide lower bounds on the security level.  Generic attacks, i.e. attacks that … Continue reading Séminaire Algorithmique : Rachelle Heim (UC Louvain, Belgique), « Generic attacks using random functions statistics »

Les travaux pionniers de Belohlavek et al. ont établi un lien convaincant entre la factorisation matricielle booléenne et l'analyse formelle des concepts, démontrant que les concepts formels servent de facteurs optimaux pour décomposer les matrices booléennes. Nous présentons une nouvelle reformulation du problème de calcul du rang booléen à l'aide de la théorie des hypergraphes, … Continue reading Séminaire Algorithmique : François Rioult, Abdelkader Ouali et Mehrad Nasernejad (GREYC), « Factorisation optimale (en taille) de matrice booléenne »