The Department Algorithms, Computation, Geometry and Image regroups 7 teams (ABC, ADAGIO, CARAMBA, GAMBLE, MAGRIT, MFX, PIXEL) that share scientific interests on these topics. Beside algorithms which is a common center of interest to all these teams (and of course to some teams of other departments as well), there are various centers of interest common to several teams. Geometry plays an important role in most teams, i.e., ADAGIO, CARAMBA, GAMBLE, MAGRIT, MFX and PIXEL. Symbolic and algebraic computing is of common interest of CARAMBA and GAMBLE, image is of interest to ADAGIO, MAGRIT and PIXEL, combinatorics and complexity also concerns several groups as ADAGIO, CARAMBA, and GAMBLE, certified computing (in a sense that requires computing with arbitrary precision) is also of common interest to CARAMBA and GAMBLE. The main common interest of ABC with the other groups is the algorithmic culture they share, though there is also some more technical connexions with other groups.
The governance of the department is managed by a board composed of the head of the department, currently Sylvain Lazard, and the team leaders.
The ABC team contributes to three different fields: machine learning, bioinformatics and statistics. Our main scientific goal is to develop the theory and practice of supervised and unsupervised learning. We focus on the theory of multi-class pattern recognition, deriving uniform convergence results which primarily deal with multi-class kernel machines such as multi-class support vector machines (M-SVMs). Our applications are in the field of biological sequence processing. More precisely, we develop theoretical bounds on the risk of classifiers, methods of model selection, multi-class support vector machines, methods for robust data mining and methods for statistical processing of biological sequences (e.g., prediction of the secondary structure of proteins).
The general goal of ADAGio is to develop efficient algorithms on discrete structures, such as strings, trees, graphs, maps, polyominoes, etc. This development comes through deep theoretical studies of combinatorial properties of those structures. Our distinguished application areas are discrete geometry and bioinformatics, in which discrete models play a crucial role. A particular attention is drawn to creating experimental software implementing algorithms we develop.
The CARAMBA team addresses the broad application domain of cryptography and cryptanalysis from the algorithmic perspective. We study all the algorithmic aspects, from the top-level mathematical background down to the optimized high-performance software implementations. Several kinds of mathematical objects are commonly encountered in our research. Some basic ones are truly ubiquitous: integers, finite fields, polynomials, real and complex numbers. We also work with more structured objects such as number fields, algebraic curves, or polynomial systems. In all cases, our work is geared towards making computations with these objects effective and fast.
The mathematical objects we deal with are of utmost importance for the applications to cryptology, as they are the background of the most widely developed cryptographic primitives, such as the RSA cryptosystem or the Diffie-Hellman key exchange. The key challenges are the assessment of the security of proposed cryptographic primitives, through the study of the cornerstone problems, which are the integer factorization and discrete logarithm problems, as well as the optimization work in order to enable cryptographic implementations that are both efficient and secure.
Classical computational geometry usually deals with linear objects in a Euclidean setting and when other situations happen, curved objects are typically linearized and non-Euclidean spaces are locally approximated by Euclidean spaces. The goals of the Gamble team are to address such limitations of classical computational geometry.
The Magrit team carries out researches in the field of computer vision, with a focus on augmented reality applications. Augmented reality is a relatively new field. It aims at augmenting the user's perception by adding in his field of view elements that improves his comprehension of his environment. Applications of this concept are plentiful and concern medical gesture assistance, learning and maintenance systems, cultural heritage, audiovisual... In order to integrate information at the right place in the user's field of view, whatever his motion, the observer's viewpoint has to be computed at every instant. Moreover, reconstructing, even partially, the observed environment is necessary to manage occlusions between the added objects and the scene or to take light interreflexions into account. Only elementary commercial applications of this concept exist to date. These applications are only effective in environments with limited user action which are furthermore often instrumented (landmarks). Many challenges remain to be tackled so as to address applications in complex environments. The Magrit team research aims at proposing robust solutions to the two main issues faced in augmented reality: viewpoint computation and reconstruction of the scene elements necessary to set up the application.
MFX focuses on challenges related to shape complexity in the context of Computer Graphics and Additive Manufacturing. We consider the entire chain from modeling, visualization to interaction and part geometry processing before fabrication. In particular, we investigate how to assist engineers and designers in creating complex geometries enforcing strict fabrication, geometric and functional requirements.
Our methodologies are rooted in procedural synthesis methods that can automatically create details within parts, under user control, such as to achieve the desired functionality after the shapes are fabricated. As the models we create are highly detailed, we develop specialized algorithms to visualize them, interact with their properties, and process their geometries before fabrication. We also investigate algorithms improving fabrication time and part quality. Our research is made available through the software developed within the team, IceSL.
Our methods have applications in both Additive Manufacturing and Computer Graphics, where the need for automatic synthesis of detailed, yet structured and functional content is constantly increasing.
PIXEL is a research team in digital geometry processing. More specifically, we are interested in parameterization techniques, meshing and reconstruction of objects from 3D point clouds. We investigate mathematically correct, scalable and numerically stable solutions, by studying the properties of the objective function in order to develop efficient optimization algorithms.
Our methods have applications in both Computer Graphics and Scientific Computing which we develop in cooperation with researchers and industrial partners from various fields. These applications include oil exploration, plasma physics, bio-chemistry and computer-aided design. Our main results are made available to the community in the form of original software.