## Special talks

The calendar of events (iCal format).

In order to add the event calendar to your favorite agenda, subscribe to the calendar by using this link.

### Previous talks

#### Year 2020

Special events

Friday February 14, 2020, 10:30AM, 3052

**Patrice Ossona De Mendez** (CAMS, CNRS/EHESS) *Low complexity networks: A model theoretical approach to sparsity, Part 11/11*

The plan of the course is:

- How complex is a graph?
- First-order Logic
- Transductions
- Sparsity I: Measuring shallow minors
- Sparsity II: Low tree-depth decompositions
- Sparsity III: Generalized colouring numbers
- Sparsity IV: Uniform quasi-wideness
- Graph theory and Logic
- Limits of graphs I: Classical limits
- Limits of graphs II: Structural limits
- Conclusion, Problems, and Discussion

Special events

Wednesday February 12, 2020, 10:30AM, 3052

**Patrice Ossona De Mendez** (CAMS, CNRS/EHESS) *Low complexity networks: A model theoretical approach to sparsity, Part 9/11*

The plan of the course is:

- How complex is a graph?
- First-order Logic
- Transductions
- Sparsity I: Measuring shallow minors
- Sparsity II: Low tree-depth decompositions
- Sparsity III: Generalized colouring numbers
- Sparsity IV: Uniform quasi-wideness
- Graph theory and Logic
- Limits of graphs I: Classical limits
- Limits of graphs II: Structural limits
- Conclusion, Problems, and Discussion

Special events

Wednesday February 12, 2020, 2PM, 3052

**Patrice Ossona De Mendez** (CAMS, CNRS/EHESS) *Low complexity networks: A model theoretical approach to sparsity, Part 10/11*

The plan of the course is:

- How complex is a graph?
- First-order Logic
- Transductions
- Sparsity I: Measuring shallow minors
- Sparsity II: Low tree-depth decompositions
- Sparsity III: Generalized colouring numbers
- Sparsity IV: Uniform quasi-wideness
- Graph theory and Logic
- Limits of graphs I: Classical limits
- Limits of graphs II: Structural limits
- Conclusion, Problems, and Discussion

Special events

Monday February 10, 2020, 10:30AM, 3052

**Patrice Ossona De Mendez** (CAMS, CNRS/EHESS) *Low complexity networks: A model theoretical approach to sparsity, Part 8/11*

The plan of the course is:

- How complex is a graph?
- First-order Logic
- Transductions
- Sparsity I: Measuring shallow minors
- Sparsity II: Low tree-depth decompositions
- Sparsity III: Generalized colouring numbers
- Sparsity IV: Uniform quasi-wideness
- Graph theory and Logic
- Limits of graphs I: Classical limits
- Limits of graphs II: Structural limits
- Conclusion, Problems, and Discussion

Special events

Friday February 7, 2020, 10:30AM, 3052

**Patrice Ossona De Mendez** (CAMS, CNRS/EHESSS) *Low complexity networks: A model theoretical approach to sparsity, Part 7/11*

The plan of the course is:

- How complex is a graph?
- First-order Logic
- Transductions
- Sparsity I: Measuring shallow minors
- Sparsity II: Low tree-depth decompositions
- Sparsity III: Generalized colouring numbers
- Sparsity IV: Uniform quasi-wideness
- Graph theory and Logic
- Limits of graphs I: Classical limits
- Limits of graphs II: Structural limits
- Conclusion, Problems, and Discussion

Special events

Wednesday February 5, 2020, 10:30AM, 3052

**Patrice Ossona De Mendez** (CAMS, CNRS/EHESSS) *Low complexity networks: A model theoretical approach to sparsity, Part 5/11*

The plan of the course is:

- How complex is a graph?
- First-order Logic
- Transductions
- Sparsity I: Measuring shallow minors
- Sparsity II: Low tree-depth decompositions
- Sparsity III: Generalized colouring numbers
- Sparsity IV: Uniform quasi-wideness
- Graph theory and Logic
- Limits of graphs I: Classical limits
- Limits of graphs II: Structural limits
- Conclusion, Problems, and Discussion

Special events

Wednesday February 5, 2020, 2PM, 3052

**Patrice Ossona De Mendez** (CAMS, CNRS/EHESSS) *Low complexity networks: A model theoretical approach to sparsity, Part 6/11*

The plan of the course is:

- How complex is a graph?
- First-order Logic
- Transductions
- Sparsity I: Measuring shallow minors
- Sparsity II: Low tree-depth decompositions
- Sparsity III: Generalized colouring numbers
- Sparsity IV: Uniform quasi-wideness
- Graph theory and Logic
- Limits of graphs I: Classical limits
- Limits of graphs II: Structural limits
- Conclusion, Problems, and Discussion

Special events

Monday February 3, 2020, 10:30AM, 3052

**Patrice Ossona De Mendez** (CAMS, CNRS/EHESS) *Low complexity networks: A model theoretical approach to sparsity, Part 4/11*

The plan of the course is:

- How complex is a graph?
- First-order Logic
- Transductions
- Sparsity I: Measuring shallow minors
- Sparsity II: Low tree-depth decompositions
- Sparsity III: Generalized colouring numbers
- Sparsity IV: Uniform quasi-wideness
- Graph theory and Logic
- Limits of graphs I: Classical limits
- Limits of graphs II: Structural limits
- Conclusion, Problems, and Discussion

Special events

Friday January 31, 2020, 10:30AM, 3052

**Patrice Ossona De Mendez** (CAMS, CNRS/EHESS) *Low complexity networks: A model theoretical approach to sparsity, Part 3/11*

The plan of the course is:

- How complex is a graph?
- First-order Logic
- Transductions
- Sparsity I: Measuring shallow minors
- Sparsity II: Low tree-depth decompositions
- Sparsity III: Generalized colouring numbers
- Sparsity IV: Uniform quasi-wideness
- Graph theory and Logic
- Limits of graphs I: Classical limits
- Limits of graphs II: Structural limits
- Conclusion, Problems, and Discussion

Special events

Wednesday January 29, 2020, 10:30AM, 3052

**Patrice Ossona De Mendez** (CAMS, CNRS/EHESS) *Low Complexity networks: A model theoretical approach to sparsity, Part 1/11*

The plan of the course is:

- How complex is a graph?
- First-order Logic
- Transductions
- Sparsity I: Measuring shallow minors
- Sparsity II: Low tree-depth decompositions
- Sparsity III: Generalized colouring numbers
- Sparsity IV: Uniform quasi-wideness
- Graph theory and Logic
- Limits of graphs I: Classical limits
- Limits of graphs II: Structural limits
- Conclusion, Problems, and Discussion

Special events

Wednesday January 29, 2020, 2PM, 3052

**Patrice Ossona De Mendez** (CAMS, CNRS/EHESSS) *Low complexity networks: A model theoretical approach to sparsity, Part 2/11*

The plan of the course is:

- How complex is a graph?
- First-order Logic
- Transductions
- Sparsity I: Measuring shallow minors
- Sparsity II: Low tree-depth decompositions
- Sparsity III: Generalized colouring numbers
- Sparsity IV: Uniform quasi-wideness
- Graph theory and Logic
- Limits of graphs I: Classical limits
- Limits of graphs II: Structural limits
- Conclusion, Problems, and Discussion

#### Year 2019

Special events

Wednesday November 20, 2019, 7PM, 3052

**Jason Li** (CMU) *The Karger-Stein Algorithm is Optimal for k-cut.*

This is a live video projection of a TCS+ talk. Live questions should be possible.

Special events

Tuesday October 22, 2019, 7PM, 3052

**Hao Huang** (Emory University) *A proof of the Sensitivity Conjecture. (live projection of TCS+ talk)*

This is a live video projection of a TCS+ talk. Live questions should be possible.

Special events

Monday June 24, 2019, 2PM, Salle 3052

**Ted Selker** (University of Maryland, Baltimore County) *User Systems Ergonomics: Contemporary human computer Interaction design*

Today we are as likely to use a computer while walking down the street as in an office. This talk will touch on classic HCI issues of simplicity focusing also on today’s need to use computers while in social circumstances.

The talk will include discussion of the relationship between functional design engineers attempt to do, aesthetic design graphic artists do, and the cognitive issues that psychologists have found to constrain design as well. Examples of physical graphical and cognitive interface will be described from Ted’s exploration of creating and testing novel interaction scenarios. Emphasis in considerate computing will be highlighted in examples from kitchens to email to automobiles.

Special events

Wednesday June 12, 2019, 7PM, 3052

**John Wright** (MIT) *NEEXP in MIP* (live video projection of TCS+ talk)*

Special events

Wednesday May 15, 2019, 7PM, 3052

**Ewin Tang** (University of Washington) *Quantum-inspired classical linear algebra algorithms: why and how? (live video projection of TCS+ talk)*

In this talk, we will discuss the motivation behind this model and its relation to existing randomized linear algebra literature. Then, we will delve into an example quantum-inspired algorithm: Gilyen, Lloyd, and Tang's algorithm for low-rank matrix inversion. This dequantizes a variant of Harrow, Hassidim, and Lloyd's matrix inversion algorithm, a seminal work in QML. Finally, we will consider the implications of this work on exponential speedups in QML. No background of quantum computing is assumed for this talk.

Special events

Wednesday April 24, 2019, 9AM, Amphitheater Turing

**Laurent Viennot, Guillaume Chapuy, Claire Mathieu, Ahmed Bouajjani, Amaury Pouly, Constantin Enea, Yves Guiraud, Jean Krivine, Hugo Herbelin** (IRIF) *Scientific talk series for the visit of Ali Charara, head of INS2I at CNRS*

The visit will be followed by a light buffet lunch.

Special events

Wednesday April 17, 2019, 7PM, 3052

**Thatchaphol Saranurak** (Toyota Technological Institute at Chicago) *Breaking Quadratic Time for Small Vertex Connectivity (live video projection of TCS+ talk)*

In this talk, I will present a randomized Monte Carlo algorithm with ~O(m + k^3 n) time. This algorithm proves the conjecture by Aho, Hopcroft, and Ullman when k=O(1) up to a polylog factor, breaks the 50-year-old bound by Kleitman, is fastest for 4 < k < n^{0.456}. The story is similar for the directed graphs where we obtain an algorithm running time at most ~O(k^2 m).

The key to our results is to avoid computing single-source connectivity, which was needed by all previous exact algorithms and is not known to admit o(n^2) time. Instead, we design the first local algorithm for computing vertex connectivity; without reading the whole graph, our algorithm can find a separator of size at most k or certify that there is no separator of size at most k “near” a given seed node.

This talk is based on joint works with Danupon Nanongkai and Sorrachai Yingchareonthawornchai.

This is a live video projection of a TCS+ talk. Live questions will be possible

Special events

Wednesday April 10, 2019, 2PM, Salle 3058

**Lélia Blin** (LIP6) *Algorithmes auto-stabilisants*

Special events

Thursday April 4, 2019, 1PM, Salle 3052

**Kais Klai** (LIPN) *Model Checking of Stuttering-Invariant Temporal Properties Using Hybrid Graphs*

Special events

Wednesday April 3, 2019, 1PM, Salle 1007

**Josef Widder** (Technische Universitaet Wien (Vienne, Autriche)) *Distributed Algorithms meet Computer-Aided Verification*

The observation that distributed algorithm theory has interesting application in computer-aided verification motivated me to explore this connection in more depth. In the second part of the talk, I will present a line of research that in the recent years led to breakthroughs in parameterized model checking of fault-tolerant broadcasting algorithms. I will close the talk by discussing ongoing research lines and open challenges.

The results on link reversal is joint work with Bernadette Charron-Bost, Matthias Fuegger, Antoine Gaillard, and Jennifer Welch. Parameterized model checking of broadcasting algorithms is joint work with Igor Konnov, Marijana Lazic, and Helmut Veith.

Special events

Friday March 29, 2019, 1PM, Salle 3052

**Duong-Hieu Phan** (XLIM, Université de Limoges) *Extractable Linearly-Homomorphic Signatures and Scalable Mix-Nets in Voting Schemes*

In this talk, we propose a new approach for proving correct shuffling based on the new notion of extractable linearly-homomorphic signature: the mix-servers can simply randomize individual ballots (meaning the ciphertexts, the signatures, and the verification keys) with an additional global proof of constant size, and the output will be publicly verifiable. The computational complexity for the mix-servers is linear in the number of ciphertexts. It also remains linear in the number of ciphertexts for the verifiers, independently of the number of rounds of mixing. This leads to the most efficient technique of mix-nets, which is at the same time highly scalable.

(Joint work with Hebant Chloé and David Pointcheval)

Special events

Thursday March 28, 2019, 1PM, Salle 3052

**Anne Etien** (LIFL) *Code transformations: two cases*

Special events

Tuesday March 26, 2019, 4PM, Salle 3052

**Marc Pouzet** (ENS Paris) *Zelus, un langage synchrone fonctionnel pour les systèmes hybrides*

Les langages synchrones décrivent des systèmes à temps discret seulement. Ils ne permettent pas de modéliser, ni fidèlement ni très efficacement des systèmes contenant des dynamiques hybrides combinant des signaux à temps discret et à temps continu. Cela créé une rupture dans la chaîne de développement, avec un langage pour la modélisation hybride et un autre pour la modélisation ou l'implémementation du logiciel de contrôle.

Dans cet exposé, nous présenterons Zelus, une extension d'un langage synchrone avec des équations différentielles ordinaires (ODEs) et une opération de détection d'événement (zero-crossing). Il permet d'écrire dans un source unique, un modèle synchrone (à temps discret) du logiciel de controle et un modèle (à temps discret où à temps continu) de son environnement. Nous illustrerons le langage sur quelques exemples. Nous présenterons son système de types qui permet de cloisonner les parties à temps discret et les parties à temps continu pour rejeter des comportements étranges que l'on obtient avec les outils de modélisation hybrides les plus utilisés. Nous montrerons également son analyse par typage des boucles de causalité par typage. Enfin, nous montrerons le principe utilisé pour générer du code séquentiel qui est lié ensuite à un solveur numérique (ici Sundials Cvode). Si le temps le permet, nous discuterons une expérimentation en cours, d'ajout de contructions de programmes probabilistes, ainsi que quelques questions ouvertes autour du typage, de la sémantique et de la vérification.

Special events

Thursday March 21, 2019, 1PM, Salle 3052

**Reem Yassawi** (Université de Lyon) *Les automates cellulaires et dynamique symbolique*

Le premier problème concerne les propriétés de randomisation de certains automates cellulaires. La randomisation asymptotique est le processus par lequel un état initial de basse entropie est asymptotiquement transformée en un état d'entropie maximale, par l’action itérée de l’automate cellulaire. Je discute des conditions nécessaires et suffisantes pour qu’une telle randomisation survienne, et aussi d'un travail récent avec Eric Rowland.

La deuxième problématique est de caractériser les automates cellulaires qui préservent un langage donné. Je résume un travail récent avec Clemens Muellner, où nous obtenons un théorème de structure pour les automates cellulaires qui préservent certains langages HD0L.

Special events

Wednesday March 20, 2019, 1PM, Salle 3052

**Lin Chen** (LRI) *Algorithm Design and Analysis in Wireless Networks*

Special events

Thursday February 21, 2019, 2PM, Salle 3052

**Pablo Arrighi** (Aix-Marseille Université) *Quantum, automata, computability and universality*

Special events

Thursday February 21, 2019, 11:45AM, Salle 1007

**Samuele Giraudo** (Université Paris-Est Marne-la-Vallée) *Graded graphs and operads*

Special events

Wednesday February 20, 2019, 1PM, Salle 3052

**Giulio Manzonetto** (LIPN) *A syntactic and semantic analysis of program equivalences*

Special events

Thursday February 7, 2019, 1PM, Salle 3052

**Sylvain Schmitz** (LSV) *The complexity of reachability in vector addition systems*

In this talk, I will explain how some of these techniques apply to reachability in vector addition systems, a landmark result in theoretical computer science, with applications in an array of fields ranging from program verification to data logics. The decidability of the problem was first shown by Mayr thanks to a decomposition algorithm. I will present succinctly the main ideas behind a tight Ackermannian complexity upper bound obtained with Jérôme Leroux for this algorithm.

#### Year 2018

Special events

Thursday September 20, 2018, 10:30AM, Amphi Turing (bâtiment Sophie Germain)

**Leonid Libkin** (University of Edinburgh) *Certain Answers Meet Zero-One Laws*

This measure is defined as the probability that the query is true under a random interpretation of missing information in a database. Since there are infinitely many such interpretations, to pick one at random we adopt the approach used in the study of asymptotic properties and 0-1 laws for logical sentences and define the measure as the limit of a sequence. We show that in the standard model of missing data, the 0-1 law is observed: this limit always exists and can be only 0 or 1 for a very large class of queries. Thus, query answers are either almost certainly true, or almost certainly false, and this classification behaves very well computationally. When databases satisfy constraints, the measure is defined as the conditional probability of the query being true if the constraints are true. This can now be an arbitrary rational number, which is always computable. Another refinement of the notion of certainty views answers with a larger set of interpretations that make them true as better ones. We pinpoint the exact complexity of finding best answers for first-order queries.

Special events

Thursday July 5, 2018, 2PM, Salle 3052

**Laurent Viennot** (Inria Paris et IRIF) *Introduction to the blockchain*

Special events

Tuesday February 20, 2018, 2PM, 3052

**Daniela Petrisan** (IRIF) *Up-To Techniques for Behavioural Metrics via Fibrations*

behavioural equivalences between systems. In this talk, I introduce up-to techniques for behavioural metrics in a coalgebraic setting and provide general results that show under which conditions such up-to techniques are sound.

For a system modelled as a coalgebra for a certain functor, the behavioural distance can be seen as a coinductive predicate using a suitable lifting of the functor. I will focus on the so called Wasserstein lifting of a functor for which we provide a new characterization in a fibrational setting. This is useful for automatically proving the soundness of up-to techniques via a generic framework developed in a previous CSL-LICS'14 paper.

I will use fibrations of predicates and relations valued in a quantale, for which pseudo-metric spaces are an example. To illustrate our framework I provide an example on distances between regular languages.

Special events

Thursday February 1, 2018, 2PM, 3052

**Vincent Danos** (ENS) *Contractivity of Markov chains (metric couplings)*

Special events

Tuesday January 30, 2018, 2PM, 3052

**Vincent Danos** (ENS) *Bayesian inversion and approximation*

Special events

Thursday January 25, 2018, 2PM, 3052

**Prakash Panangaden** (McGill University) *Quantitative equational logic and free Kantorovich algebras*

Special events

Tuesday January 23, 2018, 2PM, 3052

**Prakash Panangaden** (McGill University) *Metrics for LMPs*

Special events

Thursday January 18, 2018, 2PM, 3052

**Prakash Panangaden** (McGill University) *A dual point of view: LMPs as function transformers*

Special events

Tuesday January 16, 2018, 2PM, 3052

**Prakash Panangaden** (McGill University) *Introduction to LMPs: bisimulation, simulation, logical characterization*