Laboratoire d'informatique de l'École polytechnique

Research at LIX

The Computer Science Laboratory of Ecole Polytechnique (LIX) develops both fundamental and applied research at the best academic level in its 13 teams structured in 5 groups. At the cutting edge of math/CS interactions since its origins, LIX is now also deeply involved in fruitful industrial collaborations and its researchers are fully engaged in societal challenges.

Most of our teams contribute to the transverse thematics Fundations of Computer Science with a particular enphasis on the interactions with mathematics, Quality and Safety of Software and Communications aiming at providing the basis for an efficient, reliable and secure digital world, and Artificial Intelligence, ranging from data science to symbolic approaches through autonomous agent certification.

Proofs and algorithms

Software and hardware systems perform computations (systems that process, compute and perform) and deduction (systems that search, check or prove). The makers of those systems express their intent using various frameworks such as programming languages, specification languages, and logics. Correctness of systems is a crucial issue. It is often necessary to go further, and also to be able to guarantee efficiency of conceived solutions, which sometimes depends heavily on the used paradigm or model of computation, or of the model of the underlying system.

The group “Proofs and algorithms” aims at developing and using mathematical principles to design better frameworks for efficient and correct computations and reasoning,

We focus on foundational approaches, from theories to applications: studying fundamental problems of programming and proof theory (foundations of proof theory, semantics, computability and complexity theory, models of computations, foundations of complexity analysis for functional and imperative programming), modeling and analysis of programs and systems (invariants, temporal properties, correctness guarantees), computability and complexity theory for randomized algorithms, analog models of computations and constraint solving. One privileged field of applications concerns analog and numerical systems.

Modeling, Simulation & Learning

Contact: Marie-Paule Cani

Starting from the study of real-world objects and phenomena, our focus is on developing novel representations and algorithms for their analysis, simulation, visualization and/or design. This can result in biological models that are analyzed and used in discrete algorithms, for instance to understand or predict the behaviour of bio-molecules, in efficient methods for the computational analysis of captured visual and geometric data, as well as in the interactive construction of a variety of 3D virtual prototypes and virtual worlds that can be animated. In all cases, the methods are informed by a combination of data, prior knowledge, and mathematical modelling.

  • Team Amibio: The Algorithms and Methods for Integrative Biology (AMIBio) team is a research group in Bioinformatics contributing predictive computational methods for key questions in molecular and structural biology, with a strong expertise on (Ribo-)Nucleic Acids.

  • Team GeoViC: The Geometric & Visual Computing (GeoViC) team is a Computer Graphics and Computer Vision group tackling geometric data analysis, 3D modelling and computer animation, with applications ranging from individual shapes to complex virtual worlds.

Keywords: Bio-Informatics, Computer Graphics, Computer Vision, Discrete & Geometric Algorithm, Learning on Visual & Geometric Data

Efficient and Secure Communications

Contact: François Morain

Keywords:

This group includes two teams GRACE (INRIA/LIX) and Networks (LIX). Their ambition is the development of the “digitized society” by providing efficient and secure communications in a wide range of applications.

  • Team GRACE: GRACE mainly focuses on communication and computation security by developing researches in cryptography (number-theoretic, curve-based, code-based), cybersecurity and coding theory.

  • Team NETWORKS: The NETWORKS team is interested in all-things related to data networking, digital communication, networking architectures, network optimization and especially in constraint contexts.

Data Analytics and Machine Learning

Contact: Ioana Manolescu

Teams in the Data Analytics and Machine Learning" group carry research on novel methods for exploring, processing, analyzing and understanding complex data.

  • Team CEDAR: CEDAR focuses on rich data analytics at cloud scale. Its main research areas are: optimization and performance at scale; data exploration and insight discovery; and heterogeneous data integration. CEDAR research applies to Semantic Web graphs, high-volume data streams, business analytics, computational fact checking, polystore systems, and cloud-based data management.

  • Team Comete: The research of COMETE follows two main lines: the study of metrics to measure the leakage of information in computer systems, and methods to design of mechanisms for privacy protection that maintain the utility of data; and mathematical models to reason about the propagation of information in computer networks, and issues like group polarization and spread of fake news.

  • Team DaSciM: DaSciM research aims at advanced machine and deep learning methods for graph, text and stream data. Highlighted methods include graph degeneracy for large scale graphs, graph kernels, node/graph and set embeddings, graph isomorphisms, deep learning architectures sparsification and graph neural networks. Application domains include natural language processing (keyword extraction, event detection, opinion mining, legal texts), recommendation systems, influence maximization in social networks, academic data analysis and fraud detection.

Computer mathematics

Contact: Gregoire Lecerf

For several decades, computer science has been playing a major role in turning mathematical theories into practice for both engineering and academic research. New research areas in computer mathematics have emerged for exploring the interplay between mathematical structures and efficient algorithms. The scientific successes in these areas often rely on algorithmic advances along with efficient software implementations. As a consequence, increasingly large problems can be solved while reducing the energy consumption.

Our research group in computer mathematics stands at the crossroad of algebra, discrete mathematics, polyhedral geometry, optimization, control theory, and probability. It is organized around three teams respectively dedicated to combinatorics, computer algebra, and optimization. The group is regularly supported by academic grants, but also has close ties with industrial partners.

  • Combi team. In combinatorics, this team designs efficient techniques for the enumeration and manipulation of various discrete structures, often with a topological or geometric flavor (maps, polytopes). Among the explored applications are the limit of random discrete structures (in particular random discrete surfaces, possibly endowed with statistical physics models), the development of efficient algorithms (e.g. for random generation, mesh compression, graph drawing), and combinatorial explanations of algebraic identities.

  • MAX team. This team focuses on computer algebra and analysis, i.e. performing mathematically exact computations with objects from algebra and analysis. The research interests range from fundamental computability and complexity issues to the improvement of existing computer algebra systems that are widely used by engineers and scientists. In addition, the team develops computational software libraries (http://www.mathemagix.org) and the scientific editing platform GNU TeXmacs (https://www.texmacs.org).

  • OptimiX team. This team develops optimization methods for families of mathematical problems that are usually too difficult to be solved in an exact manner, but for which approximate algorithms often yield relevant solutions. This team focuses on pre-processing input mathematical models and on developing smart solvers from optimization and control theories. It embraces a broad expertise in mathematical modeling for industrial and societal problems, including urban mobility, traffic regulation, air transportation, molecular design, natural language processing, energy aware computations, waste water management, cloud computing, network reliability, etc.

Keywords: Asymptotic analysis, Combinatorics, Computer algebra, Control theory, Discrete structures, Distance geometry, Linear programming, Optimization, Reliable computing