Institut de Recherche en Informatique Fondamentale (IRIF)


image/svg+xml

L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université de Paris, qui héberge une équipe-projet Inria.

Les recherches menées à l'IRIF reposent sur l’étude et la compréhension des fondements de toute l’informatique, afin d’apporter des solutions innovantes aux défis actuels et futurs des sciences numériques.

L'IRIF regroupe près de deux cents personnes. Six de ses membres ont été lauréats de l'European Research Council (ERC), cinq sont membres de l'Institut Universitaire de France (IUF), deux sont membres de l'Academia Europæa, et un est membre de l'Académie des sciences.

Test of Time Award – RV’21

19.10.2021
Eugene Asarin (IRIF), Alexandre Donzé, Oded Maler, and Dejan Nickovic receive the Test of Time Award at the 21st International Conference on Runtime Verification (RV’21) for their paper Parametric Identification of Temporal Properties. Watch the RV’21 Award Announcement here.

Oded Maler Best Paper Award

14.9.2021
Eugene Asarin (IRIF), Thomas Ferrère, Dejan Ničković and Dogan Ulus receive the Oded Maler best paper award in Timed Systems at the conference Formats’2021 for their paper On the complexity of timed pattern matching.

Fête de la Science 2021 - Conference learning about cryptography

27.9.2021
From ancient history to quantum, learn about cryptography at Fête de la science in an entertaining talk by Sylvain Perifel (IRIF). Save the date, Monday October 4th, 10am at Amphitheater 1A, Halle aux farines - Campus Grands Moulins.

Ateliers-FDSL 2021

29.9.2021
IRIF researchers are participating to the 30th edition of Fête de la Science. In different schools in Paris, they will be presenting workshops and games related to computer science.

Accepted paper Eurocomb 2021 - Aubian-Charbit

3.9.2021
Guillaume Aubian, Pierre Charbit (IRIF) and Pierre Aboulker study the class of oriented graphs such that the out-neighbourhood of any vertex induces a transitive tournament and prove for it a decomposition theorem. As a consequence, they obtain that oriented graphs in this class have dichromatic number at most $2$ and satisfy Caccetta-Häggkvist conjecture.

invited-speaker-workshop-cycles

3.9.2021
Reza Naserasr (IRIF) is an invited speaker at the 29th Workshop on Cycles and Colourings. He will present a joint work with Lan Anh Pham (IRIF), Zhouningxin Wang PhD student (IRIF) and Xuding Zhu (University Jinchua): Density of C –4 -critical signed graphs. There is a classic one-to-one correspondence between (2k+1)-colorability of a graph and mapping of a specific subdivision of it to the (2k+1)-cycle. In this work they present an extension of this to 2k-coloring using homomorphisms of signed graphs.

Accepted paper Eurocomb 2021 - Naserasr-Wang

3.9.2021
Reza Naserasr and Zhouningxin Wang (IRIF) will present the notion of circular coloring of signed graphs, as a common extension of the circular coloring of graphs and the 0-free coloring of signed graphs. In this work, they consider the problem of finding the best upper bound of the circular chromatic number of restricted families of signed graphs. In particular, they show that every signed bipartite planar graph of negative-girth 6 admits a circular 3-coloring.

EUROCOMB 2021 - Three papers coauthored by IRIF PhD students

1.9.2021
Three papers coauthored by IRIF Ph.D students will be presented at the European Conference on Combinatorics, Graph Theory and Applications. Topics include oriented graphs, asymmetric hypergraphs and bipartite planar graphs.


(Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.)

Algorithmique distribuée et graphes
Mardi 26 octobre 2021, 14 heures, Salle 1007
Sagnik Sen (IIT Dharwad, India) On homomorphisms of simple signed graphs of some families

A signed graph $(G, \sigma)$ is a graph $G$ along with a function $\sigma: E(G)\to\{+,-\}$. A closed walk of a signed graph is positive (resp., negative) if it has an even (resp., odd) number of negative edges, counting repetitions. A homomorphism of a (simple) signed graph to another signed graph is a vertex-mapping that preserves adjacencies and signs of closed walks. The chromatic number (this is one of the many notions of chromatic number for signed graphs available in literature) of a signed graph $(G, \sigma)$ is the minimum number of vertices $|V(H)|$ of a signed graph $(H, \pi)$ to which $(G, \sigma)$ admits a homomorphism.

Homomorphisms of signed graphs have been attracting growing attention in the last decades, especially due to their strong connections to the theories of graph coloring and graph minors. These homomorphisms have been particularly studied through the scope of the chromatic number. In this work, we provide new results and bounds on the chromatic number of several families of signed graphs (planar graphs, triangle-free planar graphs, $K_n$-minor-free graphs, and bounded-degree graphs).

Joint work with: Bensmail, Das, Nandi, Pierron, Sopena

Sémantique
Mardi 26 octobre 2021, 10 heures 30, Exposé à distance sur Galène – salle 3052 virtuelle
Thomas Ehrhard (CNRS, Université de Paris) Coherent Differentiation [Part 1]

The differential calculus uses addition in a crucial way: this appears clearly in the Leibniz Rule. This is why the differential lambda-calculus as well as differential linear logic feature an unrestricted addition operation on terms (or proofs) of the same type. From an operational point of view, this means that these formalisms feature finite non-determinism. So a natural question arises: is non-determinism inherent to any differential extension of the lambda-calculus and linear logic? Based on intuitions coming from probabilistic coherence spaces, we provide a negative answer to this question, introducing a setting of “summable categories” where the notion of summable pairs of morphisms is axiomatized by means of a functor equipped with three natural transformations satisfying a few axioms. Then we define a notion of differentiation in such a summable category equipped with a resource modality (exponential in the sense of linear logic): this differential structure is a distributive law between a monad associated with the summability structure and the resource comonad, satisfying a few additional axioms. I will present various aspects of this theory (which features similarities with tangent categories), concrete instances of the theory as well as the syntax of a differential version of PCF which can be derived from this general categorical setting. In particular I will show that coherence spaces provide a model of this coherent differentiation, in sharp contrast with differential linear logic.

One world numeration seminar
Mardi 26 octobre 2021, 14 heures 30, Online
Michael Baake (Universität Bielefeld) Spectral aspects of aperiodic dynamical systems

One way to analyse aperiodic systems employs spectral notions, either via dynamical systems theory or via harmonic analysis. In this talk, we will look at two particular aspects of this, after a quick overview of how the diffraction measure can be used for this purpose. First, we consider some concequences of inflation rules on the spectra via renormalisation, and how to use it to exclude absolutely continuous componenta. Second, we take a look at a class of dynamical systems of number-theoretic origin, how they fit into the spectral picture, and what (other) methods there are to distinguish them.

Automates
Vendredi 29 octobre 2021, 14 heures 30, Salle 3052
Nofar Carmeli The Fine-Grained Complexity of Answering Database Queries

We wish to identify the queries that can be solved with close to optimal time guarantees over relational databases. Computing all query answers requires at least linear time before the first answer (to read the input and determine the answer's existence), and then we must allow enough time to print all answers (which may be many). Thus, we aspire to achieve linear preprocessing time and constant or logarithmic time per answer. A known dichotomy classifies Conjunctive Queries into those that admit such enumeration and those that do not: the main difficulty of query answering is joining tables, which can be done efficiently if and only if the join query is acyclic. However, the join query usually does not appear in a vacuum; for example, it may be part of a larger query, or it may be applied to a database with dependencies. We show how to use this context for more efficient computation and study how the complexity changes in these settings. Next, we aspire for an even more powerful solution for query answering: a structure that simulates an array containing the query answers. Such a structure can be used for example to enumerate all answers in a statistically meaningful order or to efficiently compute a boxplot of query answers. We call this simulation random access and study for which queries random access can be achieved with near-optimal guarantees. Our results are accompanied by conditional lower bounds showing that our algorithms can be applied to all tractable queries in some cases. Among our results, we show that a union of tractable Conjunctive Queries may be intractable w.r.t. random access, but a union of intractable Conjunctive Queries may be tractable w.r.t. enumeration.