VOOZH about

URL: https://www.irif.fr/

⇱ Bienvenue

Le conseil de laboratoire de l'IRIF, réuni le 3 mars 2026, souhaite apporter son soutien au mouvement Stand Up for Science. La motion suivante est adoptée à l'unanimité des présents.

Face aux menaces actuelles envers la libertĂ© acadĂ©mique, le financement pĂ©renne de la recherche, l’évaluation par les pairs et la dĂ©mocratie universitaire, la communautĂ© scientifique se mobilise Ă  travers l’initiative Stand Up For Science, inspirĂ©e de la situation de nos collĂšgues aux États-Unis.

L’IRIF s’associe Ă  ce mouvement pour promouvoir une recherche rigoureuse, internationale et indĂ©pendante, organisĂ©e dĂ©mocratiquement et financĂ©e de façon pĂ©renne. Elle est aujourd’hui mise en pĂ©ril, aux États-Unis, en France et ailleurs dans le monde, par des dangers variĂ©s :

  1. Attaques personnelles contre des scientifiques et des universitaires, censures, pressions ou menaces
  2. DĂ©sinformation et remise en question de faits scientifiques
  3. Diminution des postes et des moyens, fléchage trop appuyé des financements, décidés par les pouvoirs publics sans la communauté scientifique.

Cette mobilisation vise à rappeler que les sciences forment un pilier fondamental de la démocratie, garantes de notre avenir collectif.

Bienvenue

L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris Cité, et 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. Sept de ses membres ont été lauréats de l'European Research Council (ERC), trois 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.

Notion du jour

RĂ©seaux Sociaux

Suivez nous sur LinkedIn, Bluesky et Mastodon :

👁 LinkedIn
👁 Bluesky
👁 Mastodon

Actualités

👁 Prix Alonzo Church de l'EACSL

26.6.2026
FĂ©licitations Ă  Leonid Libkin (IRIF) pour l'obtention du prestigieux prix Alonzo Church de l'EACSL.

👁 https://sites.google.com/view/celt2026lix/home

18.5.2026
Epistemic logic and topological perspectives on distributed computing workshop.

June 15 to June 17, 2026 IRIF, Room 3052

Organized by : Eric Goubault (École polytechnique) and Sergio Rajsbaum (IRIF)

The goal of this workshop is to bring leaders in distributed computing, topology and epistemic logic together to foster interdisciplinary research. There has been much interest in this area, from the development of more expressive logics capable of capturing fine topological structure, to the leveraging of topological tools to represent concepts such as observations, questions, and dependence relations, and encoding deep connections with distributed computing. The richness of this area has spawned a thriving, interdisciplinary research program with applications in learning theory, network epistemology, public and private communication, inquisitive semantics, philosophy of science, artificial intelligence and knowledge representation in distributed computing, among others. This year we are envisioning new directions, in particular related to probabilistic methods.

Talks by: Alexandru Baltag, Hans van Ditmarsch, Jérémy Ledent, Sophia Knight, Yoram Moses, among others, see


(Ces actualitĂ©s sont prĂ©sentĂ©es selon un classement mĂȘlant prioritĂ© et alĂ©atoire.)

Agenda

Algorithmes et complexité
Mardi 30 juin 2026, 11 heures, Salle 3071
Suhail Sherif (LASIGE, University of Lisbon) Quantum and Classical Lower Bounds for Convex Optimization

We look at the task of epsilon-minimizing a well-behaved function f : B_d → R via querying it at points in its domain (the unit ball in d dimensions). Specifically we look at the settings where the function is convex, with varying amounts of smoothness. In these settings the problem notably exhibits a query complexity that is independent of the dimension d. When the smoothness is just a Lipschitz constraint, gradient descent is known to be the optimal classical dimension-independent algorithm. There are analogous polynomial descent algorithms that are more efficient (but were not known to be optimal) when the smoothness is a Lipschitz constraint for higher order derivatives.

We show that gradient descent and the higher-order polynomial descents are the optimal algorithms even if we are provided quantum query access to the function. To do so, we build upon a family of functions of Nemirovsky and Yudin (1983) which are very compatible with the use of the hybrid argument. This is joint work with Ankit Garg, Robin Kothari and Praneeth Netrapalli.

One world numeration seminar
Mardi 30 juin 2026, 14 heures, Online
Toghrul Karimov (MPI-SWS, IRIF) Automata on S-adic words

O. Carton and W. Thomas gave, in 2002, an algorithm for deciding whether a given automaton $A$ over infinite words accept a given morphic word $u$. Together with V. BerthĂ© and M. Vahanwala, we study the same automaton acceptance problem in the more general setting of $S$-adic words. Among other results, we show how to compute, given a set $S$ of substitutions and an automaton $A$, an automaton $B$ that accepts a sequence $s$ over $S$ if and only if $s$ directs a word accepted by $A$. Thus we are able to completely answer questions of the form “Which Sturmian words $u$ are accepted by a given automaton $A$?” In particular, we show that whether $A$ accepts $u$ is completely determined by the first $N$ (that depends only on $A$) partial quotients of the slope of $u$. Our main tools are monoids and a new (?) structure theorem for $S$-adic expansions.

Algorithmes et complexité
Mercredi 1 juillet 2026, 11 heures, Salle 3052
Marten Folkertsma (CWI Amsterdam) Fully Characterizing Lossy Catalytic Computation

A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, “catalytic” tape, which, while being available as a work tape, has the caveat of being initialized with an arbitrary string, which must be preserved at the end of the computation. Despite this restriction, catalytic machines have been shown to have surprising additional power; a logspace machine with a polynomial length catalytic tape, known as catalytic logspace (CL), can compute problems which are believed to be impossible for L.

A fundamental question of the model is whether the catalytic condition, of leaving the catalytic tape in its exact original configuration, is robust to minor deviations. This study was initialized by Gupta et al. (2024), who defined lossy catalytic logspace (LCL[e]) as a variant of CL where we allow up to e errors when resetting the catalytic tape. They showed that LCL[e] = CL for any e = O(1), which remains the frontier of our understanding.

In this work we completely characterize lossy catalytic space (LCSPACE[s, c, e]) in terms of ordinary catalytic space (CSPACE[s, c]). We show that LCSPACE[s, c, e] = CSPACE[Θ(s + e log c), Θ©]. In other words, allowing e errors on a catalytic tape of length c is equivalent, up to a constant stretch, to an equivalent errorless catalytic machine with an additional e log c bits of ordinary working memory.

SĂ©minaire des membres non-permanents
Jeudi 2 juillet 2026, 16 heures, Salle 3052
Alejandro Polo Molina Non encore annoncé.

Algorithmes et complexité
Mercredi 8 juillet 2026, 14 heures, Salle 3052
Clément Canonne (University of Sydney) Verification of Statistical Properties from Sensitive Data

Analyzing (very) large datasets to build accurate models is the workhorse of machine learning and underlies most of the advances in AI/ML over the past decades. These datasets are increasingly seen as valuable assets, e.g., due to the difficulty in obtaining them (sensitive, regulated, or carefully curated user data), generating them (computation-heavy processes), or trusting them (poisoning attacks). For companies owning such datasets, this leads to a thorny issue: how to convince interested customers that a dataset is reliable and has the application-specific statistical properties they need, while revealing as little data as possible?

In this talk, I will discuss a recent line of work, from the theoretical computer science community, aimed at designing principled approaches to address this problem: Proofs of Proximity for Distribution Testing, and some of its various variants (!).

Based on work by other people, as well as recent and ongoing work with Abigail Gentle, Sam Polgar, Aditya Vikram Singh, Aravind Thyagarajan, and Joy (Qiping) Yang.

Théorie des types et son implémentation
Mercredi 8 juillet 2026, 14 heures, Salle 3052
Kazuhiko Sakaguchi (ENS Lyon) Non encore annoncé.

👁 Image