2012/2013
- 2013-06-18Sinai Robins (Nanyang Technological University (Singapore))
This is joint work with Winfried Kohnen and Amanda Folsom.
- 2013-06-11Henri Cohen (imb)A first package for modular forms in Pari/GP
- 2013-05-28Achill Schürmann (Universität Rostock)Exploiting Symmetries in Polyhedral Computations
Many important problems in mathematics and its applications are modeled using linear constraints respectively polyhedra. Standard modeling often yields polyhedra having many symmetries. However, standard algorithms do not take advantage of them, and even worse, they often work particularly poorly on symmetric problems. In this talk we give an overview about ongoing work on new symmetry exploiting techniques for three fundamental task in polyhedral computations: the representation conversion problem, integer linear programming, and lattice point counting.
Initial proof-of-concept results show that affine symmetries can be exploited quite well in certain situations. In order to apply these new techniques on a broader scale new theoretical grounds have to be broken.
- 2013-05-14Maike Massierer (University of Basel)Point Compression for the Trace Zero Variety
The hardness of the (hyper)elliptic curve discrete logarithm problem over extension fields lies in the trace zero variety. A compact representation of the points of this abelian variety, computed by a point compression algorithm, is needed in order to accurately assess the hardness of the discrete logarithm problem there. Such algorithms have been proposed by Lange and Silverberg. We present a new representation that is optimal in size, compatible with the structure of the variety, and allows efficient point compression and decompression.
- 2013-04-26Sandi Klavzar (University of Maribor, Slovenia)
- 2013-04-23Pierre Chrétien (imb)
Soit $K/\mathbb{F}_q$ un corps de fonctions d’une variable et $S$ un ensemble non vide de places $\mathbb{F}_q$-rationnelles de $K$. Le $S$-corps de classes de Hilbert de $K$ est la plus grande extension abélienne non ramifiée de $K$ dans laquelle se décomposent complètement les places de $S$. On décrira une méthode efficace de calcul du $S$-corps de classes de Hilbert pour $K$ de genre non nul, basée sur l’étude de ses automorphismes sur $\mathbb{F}_q$. On illustrera cette méthode par le calcul de $S$-corps de classes de Hilbert de courbes de Deligne-Lusztig ainsi que certains de leurs $S$-corps de classes de rayons.
- 2013-04-16Ralf Klasing (Labri)Identifying coDes in Evolving grAphs (IDEA).
In this talk, we will give an overview of the ANR project “Identifying coDes in Evolving grAphs (IDEA)”. In particular, we will present some of the results obtained in the project, and we will outline some potential directions of future research.
- 2013-04-09Pierre Lezowski (imb)Groupe de classe d'Arakelov
- 2013-04-05Christophe Ritzenthaler (Université Aix-Marseille)Sur la distribution des traces des courbes de genre 3 sur les corps finis
A une variété abélienne principalement polarisée de trace $t$ sur $\mathbb{F}_q$ et qui est géométriquement la jacobienne d’une courbe non-hyperelliptique, on peut associer une courbe sur $F_q$ de trace $t$ ou (exclusif) de trace $-t$. Si on note $N_{q,g}(t)=\{$ classes d’isomorphismes des courbes de genre $g$ et de trace $t$ sur $\mathbb{F}_q$ $\}$, la différence $V_{q,g}(t)=N_{q,g}(t)-N_{q,g}(-t)$ quantifie le phénomène précédent. Je donnerai dans cet exposé les premières évidences qu’en genre $3$, $V_{q,g}(t)$ semble être gouvernée par une fonction bien précise.
Travail en commun avec Reynald Lercier, Florent Rovetta, Jeroen Sijsling et Ben Smith
- 2013-03-29Florent Foucaud (Universitat Politècnica de Catalunya)The complexity of signed graph homomorphisms.
Signed graphs are graphs with signed edges (i.e. positive and negative) with an equivalence relation based on a re-signing operation. They have been used, for example, as a way of extending classical results in graph colouring (in relation with graph minors) or in the theory of flows. Recently, the notion of homomorphisms of signed graphs has been introduced by Bertrand Guenin and further developed by Reza Naserasr, Edita Rollova and Eric Sopena. It naturally extends the notion of homomorphisms for classical graphs to the case of signed graphs. We study the computational complexity of the $H$-signed colouring problem, i.e. the question of deciding whether a given signed graph admits a homomorphism to a fixed signed graph $H$. We settle all cases where $H$ is a cycle, and discuss the restriction where the input graph is planar. We relate these questions to the state of the art for classical graph homomorphisms. This is joint work with Reza Naserasr.
- 2013-03-25Guillem Perarnau (Universitat Politècnica de Catalunya)A probabilistic approach to consecutive pattern avoiding in permutations
We present a new approach based on the probabilistic method, for the problem of enumerating permutations of length n that avoid a fixed consecutive pattern of length m. We use this approach to give alternative and shorter proofs for some known results as well as to provide new results that have not been shown using other techniques.
- 2013-03-22David Lubicz (CELAR — Rennes)Algèbre linéaire sur $\mathbb{Z}_p[[u]]$ et application au calcul de réseaux dans les représentations galoisiennes p-adiques.
Soit $R$ un anneau de valuation complet et $S=R[[u]]$. Dans cet exposé, nous expliquons comment calculer efficacement les opérations habituelles telles que la somme ou l’intersection de sous-$S$-modules de $S^d$. Comme $S$ n’est pas principal, il n’est pas possible d’obtenir une borne uniforme sur le nombre de générateurs des modules résultant de ces opérations. Nous expliquons comment contourner ces problèmes, suivant une idée d’Iwasawa, en calculant une approximation du résultat de ces opérations à un quasi-isomorphisme près.
Nous donnons une application au calcul de réseaux dans les représentations Galoisiennes p-adiques.
- 2013-03-19Claus Diem (Leipzig)Systèmes linéaires spéciaux sur courbes et le problème du logarithme discret
- 2013-03-05Paul Dorbec (Labri)A propos de domination dans les graphes.
Au cours de cet exposé, nous verrons les bases de la domination dans les graphes et quelques pistes de recherches actuelles. Nous parlerons en particulier de la conjecture de Vizing, de dominants parfaits (codes couvrants), et de différentes autre variantes de la domination.
- 2013-02-26Marie-Françoise Roy (Rennes)
Complexity of deciding connectivity in semi-algebraic sets: recent results and future research directions
The number of connected components of a real algebraic set is $O(d)^k$ which is polynomial in the degree $d$ and singly exponential in the number of variables $k$. The first algorithm with elementary recursive complexity for counting the connected components is Collins’s cylindrical decomposition, with complexity doubly exponential in $k$. Canny’s roadmap gives a singly exponential complexity, its best variants have complexity $d^{0(k^2)}$. The talk will report on recent results based on work of Safey/Schost and Basu/Roy/Safey/Schost improving Canny’s roadmap using a baby step giant step strategy and obtaining complexity $d^{0(k \sqrt(k))}$. A challenging research direction is to use a divide and conquer strategy to get an exponent quasi linear in $k$.
- 2013-02-19Tony Ezome (Université de Masuku — Franceville, Gabon)
- 2013-02-05Sorina Ionica (ENS Paris)
The CRT method for computing class polynomials in genus 2 relies on algorithms for traveling in the isogeny graph and endomorphism ring computation. Using Galois cohomology, we relate the endomorphism ring structure to certain properties of the $\ell$-Tate pairing, such as non-degeneracy on subgroups of the $\ell$-torsion giving kernels of isogenies of principally polarized abelian varieties in the $\ell$-isogeny graph. In genus 2, we present an efficient method to check whether the jacobian has locally maximal endomorphism ring at $\ell$. In view of application to the CRT method for class polynomials, we derive an algorithm to compute horizontal $\ell$-isogenies starting from a jacobian with maximal endomorphism ring.
- 2013-01-29Nicolas Mascot (imb)Calcul de représentations galoisiennes modulaires
Je décrirai un algorithme permettant de calculer les représentations galoisiennes associées à une forme modulaire parabolique propre, et j’étudierai un problème associé, à savoir le calcul des coefficients de Fourier de cette forme modulo un petit nombre premier.
- 2013-01-22Hamish Ivey-Law (imb)
- 2013-01-18Bill Allombert (imb)
- 2013-01-18Charles Boyd
- 2013-01-18Karim Belabas (imb)
- 2013-01-17Denis Simon (Caen)
- 2013-01-17Philipe Elbaz-Vincent (Grenoble I)Computing with lattices and arithmetic groups
- 2013-01-17François Brunault (ENS Lyon)
- 2013-01-17Christophe Delaunay (Université de Franche-Comté)
- 2013-01-16Bill Allombert (imb)
- 2013-01-16Charles Boyd
- 2013-01-16Loïc Grenié (Università di Milano-Bicocca)
- 2013-01-16Karim Belabas (imb)
- 2013-01-16Karim Belabas (imb)
- 2013-01-15Pacal Molin (Université Paris 7)PARI $L$ functions
- 2013-01-15Bill Allombert (imb)
- 2013-01-15Bill Allombert (imb)
- 2013-01-14Karim Belabas (imb)
- 2013-01-14Henri Cohen (imb)
- 2013-01-14Jürgen Klüners (Universität Paderborn)
- 2013-01-14Xavier Roblot (Université Claude Bernard Lyon I)
- 2013-01-14Eduardo Friedman (Universidad de Chile)Anomalies of zeta-regularized products and determinants
- 2013-01-08Philippe Jaming (imb)Problème de la phase dans le cadre discret
Nous étudions le problème de reconstruire une fonction à partir du module de sa transformée de Fourier (discrète) et d’informations a priori sur la fonction. Par exemple, dans le cas où la fonction est la fonction caractéristique d’un ensemble $A$, on veut reconstruire $A$ à partir de l’ensemble de différences $A-A$.
- 2012-12-14Christine Bachoc (imb)Le nombre thêta de Lovász : applications, généralisations, et problèmes ouverts II
Nous ferons un petit tour d’horizon des applications en théorie des codes et en géométrie euclidienne du nombre thêta de Lovász, une introduction a la hiérarchie de Lasserre des programmes SDP pour le nombre d’indépendance d’un graphe dont thêta est le premier niveau, et nous présenterons quelques questions ouvertes.
- 2012-12-07Pierre Lezowski (imb)Questions d'Euclidianité
- 2012-12-07Christine Bachoc (imb)Le nombre thêta de Lovász : applications, généralisations, et problèmes ouverts I
Nous ferons un petit tour d’horizon des applications en théorie des codes et en géométrie euclidienne du nombre thêta de Lovász, une introduction a la hiérarchie de Lasserre des programmes SDP pour le nombre d’indépendance d’un graphe dont thêta est le premier niveau, et nous présenterons quelques questions ouvertes.
- 2012-12-07Jean-Marc Couveignes (imb)Vous trouvez ça complexe? Tant mieux!(in the Inria Unithé ou café seminar)
S’il y a bien un domaine où l’on puisse dire « c’est compliqué et tant mieux! » il s’agit de la science du secret. Et plus exactement au sein de la science du secret, c’est-à-dire la cryptologie, la protection des communications et des données numériques. Par exemple lorsqu’on envoie un sms, il y a un système de cryptage, sans lequel mon message pourrait être intercepté par n’importe qui. Lorsqu’un message est crypté (comme c’est donc le cas des sms), il est impératif qu’il soit facile à décrypter pour le destinataire, qui connaît la clé, et difficile pour celui qui ne la connaît pas. Et c’est là qu’intervient la théorie de la complexité! Elle permet de distinguer les questions faciles des questions difficiles. Enrichie par la combinatoire et la théorie des nombres, elle sous-tend la cryptologie moderne et garantit la confidentialité et l’authenticité des communications numériques comme nous l’expliquera Jean-Marc Couveignes, chercheur de l’équipe Lfant.
- 2012-11-27Jacques Martinet (imb)
Soit $E$ un espace euclidien de dimension $n$. L’invariant d’Hermite d’un réseau $\Lambda \subset E$ est $\Gamma(\Lambda)=\frac{\min\Lambda}{\det(\Lambda)}$.
On s’intéresse à $\Gamma’(\Lambda):=(\Gamma(\Lambda)\Gamma(\Lambda^*))^{1/2}$, dont l’introduction a été motivée par les classes jumelles de Zimmert, et à ses maxima sur l’espace des réseaux, dont la classification n’a été faite que jusqu’à la dimension~$4$. On considérera aussi un problème voisin non résolu à partir de $n=4$. Les ordinateurs ne connaissant pas les réseaux, les questions abordées doivent être traduites en termes de matrices symétriques.
La méthode proposée repose sur une décomposition de l’espace des réseaux en classes minimales, correspondant à la décomposition cellulaire de l’espace des formes quadratiques définies positive, connue jusqu’à la dimension $7$ ($n=5$: Batut; $n=6,7$: Elbaz-Vincent—Gangl—Soulé).
- 2012-11-20Bill Allombert (imb)
La version de Harley de l'algorithme de Satoh permet de compter les points sur une courbe elliptique ordinaire sur $\mathbb{F}_p$ en temps $\tilde{O}_p(n^2)$ pour tout $p$. Nous montrons qu’il est possible d’obtenir une complexité en $\tilde{O}(p^2 n^2)$ et nous proposons une implantation dans
PARI/GP. - 2012-10-30Luca De Feo (Université de Versailles Saint-Quentin-en-Yvelines)Il est bien connu que certains graphes de courbes elliptiques isogènes ont une structure de graphe de Ramanujan, ce qui garantit des bonnes propriétés de mixage pour les marches aléatoires. Cette observation a été utilisée à plusieurs reprises pour construire des cryptosystèmes basés sur la difficulté supposée de calculer une isogénie entre deux courbes elliptiques données.
Parmi ces protocoles, nous nous intéressons particulièrement à l'échange de clef de Rostovstev et Stolbunov: il s'agit essentiellement d'un protocole de Diffie-Helman basé sur l'action du groupe des classes sur un graphe d'isogénies ordinaires. Ce protocole est peu efficace et présente un intérêt purement théorique; les auteurs ont suggéré qu'il pourrait être utilisée dans un contexte post-quantique, cependant Childs, Jao et Soukharev ont montré qu'il est attaquable en temps sous-exponentiel quantique à cause de sa structure abélienne.
Dans ce travail, en commun avec David Jao et Jérôme Plût, nous proposons un noveau protocole à la Diffie-Helman basé sur des marches dans des graphes d'isogénies supersingulières. La similitude avec le protocole de Rostovstev et Stolbunov est seulement superficielle: dans notre cas il n'y a pas de structure abélienne agissant sur le graphe, ce qui nous oblige à passer de l'information supplémentaire pour réaliser l'échange. Cependant il ne semble pas y avoir de moyen d'utiliser cette information supplémentaire pour attaquer le protocole, et l'absence d'une structure abélienne défie toute attaque quantique. La séparation la plus significative entre notre construction et les échanges de Diffie-Helman est réalisée par un protocole Zero-Knowledge que nous construisons au dessus de nos primitives, et dont l'équivalent abélien est trivialement cassé.
Notre protocole, déjà dans une implantation naïve en Magma, est sensiblement plus performant que celui de Rostovstev et Stolbunov. Son optimisation est aussi intéressante que le protocole lui même; en effet une étude fine de la combinatoire du calcul d'isogénies se réduit naturellement à des problèmes d'optimisation pour des arbres binaires (infinis) avec poids. En combinant cette étude avec des techniques classiques en arithmétique des courbes elliptiques, nous obtenons une implantation mixte en Sage/Cython/C 1000 fois plus rapide que le protocole de Rostovstev et Stolbunov et avec des performances comparables à celles de nombreux protocoles à base de couplages.
- 2012-10-23Henri Cohen (imb)
- 2012-10-16Karim Belabas (imb)Tomographie arithmétique
- 2012-10-09Fernando Mario (Berlin)Packings of bodies in Euclidean spaceGiven a finite list of convex bodies in Euclidean space, a packing is a union of nonoverlapping translated copies of the bodies given. A natural question concerning packings is how dense they can be made, that is, what is the maximum fraction of space that can be covered by a packing of some given bodies?
I wil show how harmonic analysis and semidefinite programming can be used to give upper bounds for the maximum density of a packing of bodies. In particular I will discuss the case of binary sphere packings, when one considers packings of spheres of two different sizes, and show how the computer can be used to find upper bounds for the densities of such packings.
This is joint work with David de Laat and Frank Vallentin.
- 2012-10-02Fabien Pazuki (imb)Décompositions en hauteurs locales sur les courbes elliptiques II
- 2012-09-25Fabien Pazuki (imb)Décompositions en hauteurs locales sur les courbes elliptiques ILe but de l'exposé est de donner un éclairage sur des travaux de Cremona, Prickett et Siksek concernant le calcul de générateurs du groupe de Mordell-Weil. On révisera le cadre théorique puis on abordera les aspects pratiques de leurs articles. On discutera enfin des généralisations futures.
- 2012-09-18Karim Belabas (imb)Calcul de résidus de la fonction zeta
- 2012-09-11Enea Milio (Montpellier)Techniques de criblage pour la factorisation et le calcul de logarithmes discretsAujourd'hui, les meilleurs algorithmes pour résoudre les problèmes de la factorisation (NFS) et du logarithme discret (NFS-DL) dans le groupe multiplicatif d'un corps fini utilisent la notion de crible sur un corps de nombres (number field sieve). Nous nous proposons de décrire les différents aspects de ces algorithmes.