Séminaire MAGMAT, Vendredi 20 février

Nous accueillons Antoine Deza qui est depuis peu professeur à Orsay.

On the polynomial Hirsch conjecture and its continuous analogue

The simplex and primal-dual interior point methods are the most computationally successful algorithms for linear optimization. While simplex methods follow an edge path, interior point methods follow the central path. Within this framework, the curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. In this talk, we highlight links between the edge and central paths, and between the diameter and the curvature of a polytope. We recall continuous results of Dedieu, Malajovich, and Shub, and discrete results of Holt and Klee and of Klee and Walkup, as well as related conjectures such as the Hirsch conjecture that was disproved by Santos. We also present analogous results dealing with average and worst-case behaviour of the curvature and diameter of polytopes, including a result of Allamigeon, Benchimol, Gaubert, and Joswig who constructed a counterexample to the continuous analogue of the polynomial Hirsch conjecture. Based on joint work with Tam ́as Terlaky (Lehigh), Feng Xie(Microsoft), and Yuriy Zinchenko (Calgary).

 Imprimer  E-mail

Séminaire MAGMAT, Vendredi 13 février

Ce vendredi nous accueillerons Stefan Mengel du Lix.
L'exposé aura lieu en salle 301 à 10h30. Venez tout apprendre des SAT solver modernes et de langages de représentations de formules DNF/CNF,
le tout matiné de graphs expander.

Expander CNFs have Exponential DNNF Size

DNNFs are a class of Boolean circuits studied in the area of knowledge compilation in artificial intelligence where they serve as a target language into which knowledge bases are compiled. DNNFs form a very general language; in articular they generalize classical languages like OBDDs and DNF-formulas. While it was known that under standard complexity theoretic assumptions CNF formulas can generally not be compiled into DNNFs without a superpolynomial size blow-up, no concrete, unconditional lower bounds were known for DNNFs. In joint work with Simone Bova, Florent Capelli and Friedrich Slivovsky, we showed such a lower bound, proving that there are CNF-formulas of size linear in the number of variables that cannot be compiled into DNNFs of subexponential size. In this talk I will give and introduction into the area, explain our result, describe the hard CNF formulas and sketch some of the key parts of the proof.

 Imprimer  E-mail

Séminaire CRYPTO: mercredi 11 février

Alberto Battistiello (Oberthur, UVSQ).

Common Points on Elliptic Curves: The Achille's heel of fault attack countermeasures.

Elliptic curve cryptosystems offer many advantages over RSA-like cryptography, such as speed and memory saving. Nonetheless the advent of side-channel and fault-injection attacks mined the security of such implementations. Several countermeasures have been devised to thwart these threats, so that simple attacks on state-of-the-art secured implementations seem unlikely. We took up the challenge and show that a simple fault attack using a very relaxed fault model can defeat well known countermeasures. After introducing the notion of common points, we exhibit a new fault-injection attack that breaks state-of-the-art secured implementations. Our new attack is particularly dangerous since no control on the injected error is required and only one fault is sufficient to retrieve the secret.

 Imprimer  E-mail

Séminaire MAGMAT, Vendredi 23 Janvier

Ce vendredi nous accueillons Marie-Pierre Gaigeot du Laboratoire Analyse et Modélisation pour la Biologie et l'Environnement (Université d’Évry).
L'exposé aura lieu à 10h30 en salle 301. Venez nombreux pour voir un exemple de recherche transdisciplinaire.

Simulations de dynamique moléculaire ab initio: quels systèmes, pour quelles applications ?

Je présenterai la méthode de dynamique moléculaire ab initio dans la représentation de la fonctionnelle de la densité (DFT) et les applications d'intérêt dans notre groupe au laboratoire LAMBE de l'Université d'Evry val d'Essonne. Je montrerai comment nos simulations sont systématiquement employées pour aider à l'interprétation fine d'expériences de caractérisation d'états de la matière. Nous verrons en particulier des simulations de la spectroscopie anharmonique de molécules et clusters en phase gazeuse en lien avec les expériences IR-PD et IR-MPD, et des simulations d'interfaces solide d'oxide-eau liquide en lien avec des expériences de spectroscopie SFG. Nous verrons également quels développement venant de collaborations avec des équipes d'algorithmique (au PRISM) sont nécessaires pour automatiser certaines de nos analyses de trajectoires.

 Imprimer  E-mail

Soutenance de thèse: Mohamed Lamine Lamali

Qualité de service et calcul de chemins dans les réseaux inter-domaine et multicouches


 Résumé : 

La Qualité de Service (Quality of Service - QoS) est une garantie de paramètres réseau (bande passante élevée, délai court, etc.). Dans un réseau inter-domaine, elle peut être assurée par des contrats entre domaines appelés Service Level Agreements (SLA). Dans cette thèse, nous nous intéressons d’abord à l’étape de négociation de SLA : la sélection des SLA proposés par un domaine. Nous proposons des méthodes exactes et approchées permettant aux domaines de proposer les SLA qui maximisent leurs revenus. Nous étudions également l'impact de la réputation des domaines sur cette négociation. Au niveau de l’instanciation des SLA, nous nous intéressons au calcul de chemins qui prennent en compte les encapsulations de protocoles (afin de pallier l’hétérogénéité technologique des domaines). En utilisant des outils de théorie des langages, nous proposons la première solution polynomiale au calcul de chemins dans un tel contexte.

Lire la suite

 Imprimer  E-mail

DMC Firewall is developed by Dean Marshall Consultancy Ltd