Séminaire MAGMAT, Vendredi 20 Mars

Ce vendredi, nous aurons un séminaire à 10h30 en salle 301.
Arnaud Mary (Université de Lyon) viendra nous faire un exposé intitulé:

Dualisation multi-objectifs et applications en biologie.

Un hypergraphe $H$ est un couple formé d'un ensemble de sommets $V$ et d'une famille de sous-ensembles de $V$ appelés les hyperarêtes de $H$. Un transversal d'un hypergraphe est un sous-ensemble de sommets qui intersecte toutes les hyperarêtes de l'hypergraphe. Étant donnés deux hypergraphes $H_1$ et $H_2$ sur un même ensemble de sommets $V$, le problème de dualisation multi-obectif consiste à trouver tous les transversaux de $H_1$ qui intersectent un ensemble minimal d'hyperarêtes de $H_2$. Ce problème trouve plusieurs applications en biologie notamment dans la recherche de facteurs de transcription impliqués dans la mauvaise régulation de gènes au sein d'une tumeur.

 Imprimer  E-mail

Séminaire MAGMAT, Vendredi 6 Mars

Ce vendredi, nous aurons un séminaire à 10h30 en salle 301.
Joseph Salmon (Télécom Paris) viendra nous faire un exposé intitulé:

Mind the (duality) gap: safer rules for the Lasso.

The Lasso is an l1-regularization technique for least-square, having the nice property of inducing sparse solutions. Recently, screening variables has been considered to speed up optimization algorithms solving a Lasso problem or its derivatives.  We propose new versions of the so called safe rules for the Lasso. Based on duality gap considerations, our new rules create safe test regions whose diameters converge to zero for any solver outputting a converging sequence toward a Lasso solution. This helps screening out more variables for a wider range of tuning parameters. In addition to faster convergence to a solution, we prove that we correctly identify active sets (supports) in finite time. Though our framework can encompass any solver, we have implemented our strategies on a popular coordinate descent version. We achieved noticeable computing time reduction with respect to former safe rules.

 Imprimer  E-mail

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

  • 1
  • 2
DMC Firewall is developed by Dean Marshall Consultancy Ltd