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 poles. 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

Contact: Olivier Bournez

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 pole “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

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

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.

Efficient and Secure Communications

Contact: Guénaël Renault

Keywords:

This pole 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

Keywords:

Teams in the Data Analytics and Machine Learning" pole 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.

Combinatorics and computer algebra

Contact Gregoire Lecerf

Keywords: Algebraic combinatorics, Asymptotic analysis, Computer algebra systems, Control theory, Differential algebra, Discrete structures, Enumerative combinatorics, Geometry of combinatorics, Polynomial systems, Reliable computing, Scaling limits, Signal processing, Symbolic computations

Modern combinatorics and computer algebra share common roots in algebra and discrete mathematics, and have both enjoyed a rapid growth during the last decades with the advent of computational technologies.

Historically, combinatorics was essentially focused on counting discrete structures and proving related algebraic identities, for instance with balls and urns problems involving binomial coefficients. Nowadays it has a much wider spectrum as it embraces the enumeration, analysis and efficient manipulation of trees, permutations, graphs, maps, and various algebraic structures. Combinatorics takes a central place in theoretical computer science, especially in the complexity analysis of probabilistic algorithms and the asymptotic analysis of random processes. Applications and other strong connections occur mostly within statistical physics, applied algebra, number theory, probability theory, topology, and computational geometry.

A central purpose of computer algebra is the design of fast algorithms for basic mathematical objects: integers, polynomials, series, and matrices. On the top of them higher mathematical problems are studied from computability and complexity point of views. This concerns various areas from symbolic computations, commutative and non-commutative algebra, algebraic geometry, algebro-differential problems, etc. The goal is the design of fast algorithms that always compute exact and guaranteed solutions. Computer algebra further involves software development, either into dedicated standalone libraries, or within so called generalist and user friendly “computer algebra systems”, that are widely used in research and development. Applications potentially concern many areas, and so far the strongest connections occur in cryptography, error correcting codes, number theory, robotics, control theory, and signal processing.

  • Team Combi: In combinatorics we design efficient techniques for the enumeration and manipulation of various discrete structures, often with a topological or geometric flavour (maps, polytopes). Among the applications we explore, we study the limit of random discrete structures (in particular random discrete surfaces, possibly endowed with statistical physics models), develop efficient algorithms (e.g. for random generation, mesh compression, graph drawing), and give combinatorial explanations of algebraic identities.

  • Team MAX: Research in computer algebra covers computability and complexity issues with mathematical objects, in order to calculate in an exact manner. Our results generally aim at improving existing computer algebra systems, that are widely used by engineers and scientists. We further deal with specific applications in control (e.g. traffic regulation on freeways) and signal theory. We develop our own computational software libraries (http://www.mathemagix.org) along with friendly graphical interfaces; see our scientific editing platform GNU TeXmacs at https://www.texmacs.org.