SéPAG (Séminaires de ParSys, A&O et GaLAC) are seminars organized by the PhD students of the AAC departement at the LISN. They aim to share their research work in a popularized way. These seminars take place every other Wednesday at 2:00pm in room 455, building 650. They are open to the PhD students and post-docs of AAC. You can join our mailing list to be informed of future seminars!
Quantum Introduction
Julien Rauch (ParSys)
We’re hearing more and more about quantum computing. Between press announcements and colossal investments by various countries, it’s now one of the hottest topics on the news. Everyone’s heard of quantum computing, but who really knows what it means? Here’s a short introduction to quantum computing and the mathematical model of quantum gates.
Proof of inclusion in NP of a neural network decision problem
Valentin Dardilhac (GALaC)
Some NP-complete problems are harder to prove to be hard than to be in NP. We will illustrate that with an example of inclusion in NP: the decision problem arround training a neural network with a single neuron and activation function ReLU.
Léo Kulinski (GALaC)
Musical juggling consists of producing music by the very act of juggling. In this context (stemming from a collaboration between computer science researchers at LISN and a juggling artist), we refer more specifically to juggling with balls that each produce a musical note when caught. The aim of this seminar is to present this thesis that delves at the same time into theoretical and practical aspects. On the one hand, given a melody, we would like to find how it can be juggled. A mathematical and combinatorial framework called siteswap was established in the 80s to describe juggling patterns. We’ve expanded it to its musical equivalent, paving the way for the use of juggling automatas, backtracking algorithms, and reductions to problems such as Exact Cover or SAT. On the other hand, we have to keep in mind the jugglers we are working with, since they are the recipients of the tools we are developing. Indeed, their needs for practical and artistic juggling patterns lead the constraints of our search. Moreover, they are both creators of juggling shows who need a software to customise musical juggling patterns, and performers who need to learn, memorise and train those patterns, for which we may be able to assist through HCI (Human Computer Interaction).
📄 Introduction to Open Science
Solal Nathan (A&O)
Starting with the definitions, going through the legal bases in France and Europe, and even exploring the publishing mafias, I propose a journey into the territory of open science.
Characterisations of polynomial-time and polynomial-space classes
Manon Blanc (Lix and GALaC)
Computability and complexity are two fields of theoretical computer science, widely studied a few decades ago. Today, because of the need of modelling various problems with computers, we study them again: For example, if you use an embedded system for, say, an autonomous car, you need to have to be sure it can do all the computations, on time. After introducing the basics of those fields, we will see several ways to characterise complexity classes, so they can be effectively used.
📄 Interpreting the Inner Workings of Deep Neural Networks through Concept-based Explanation
Cyriaque Rousselot (A&O)
In our digital era, algorithms govern numerous aspects of our lives, offering services, content, and resources. Establishing trust with those algorithms is crucial to safeguard users against harmful bias and catastrophic failures, particularly in critical situations. Explainable Artificial Intelligence (XAI) emerges as a vital research domain aiming to unravel and interpret the workings of black box models. In this presentation, we delve into the concept of black box models and explore cutting-edge advancements in Concept-based explanations that try to shed light on the inner workings of deep neural networks.
📄 A short introductions to the mixed precision paradigm
Matthieu Robeyns (ParSys)
Low-precision calculations give a significant speed-up to AI and quantum computing. However, the results will be less accurate, so to compensate for this inaccuracy we will use the mixed precision.
📄 Programming Project Management
Solal Nathan (A&O)
There is a lot to handle when you want to produce high quality code. It needs to be legible so you (the future you) and your collaborator can come back to it. It needs to be documented in order to be reproduced by your pairs. Sometimes it require to use a few extra tools and to learn some good habits. Today, we will talk about practical project management.
An Invitation to the Domino Problem
Nicolas Bitar (GaLAC)
Since their introduction in the 60s, Wang tiles have served as a useful model of computation. Perhaps their most famous role is in The Domino Problem: Given a set of tiles, can we determine if they tile the plane? In this talk we will survey a bit of the history of this problem and show how tiling with local rules allows to create aperiodicity and embed computation in the plane. We will also briefly explore what happens in different dimensions.
An exploration of quasi-optimal tensor contraction strategies for dot-product in tensor train format (poster)
Matthieu Robeyns (ParSys)
Adrien Pavao (A&O)
The ranking problem arises in many situations: when friends want to pick a restaurant, in political elections or when trying to rank algorithms based on their performance on a set of tasks. Even if this is a fundamental problem, there are many different ranking methods, and the truth is, none is perfect. What is so hard about this problem? What can we do in practice? Let’s dive into the theoretical properties of such ranking functions.
📄 Follow the Sturmian rabbit: decidability in the substitutive model
Pierre Béaur (GaLAC)
In the movie Matrix, the hero Neo often sees the world as endless binary sequences: but how can sequences of 0 and 1 encode the universe? In theoretical computer science, it is symbolic dynamics that answers these questions, and more precisely combinatorics of words. In this talk, I will explain how to measure the complexity of an infinite binary word, how calculators discretize a line, and I will present the mathematical and algorithmic properties of a fundamental model of word combinatorics: substitutive words.
📄 Job Recommender Systems: challenges and pitfalls
Solal Nathan and Guillaume Bied (A&O)
Recommending jobs has the potential to reduce frictional unemployment and empower job seekers. In this talk, we present an ongoing interdisciplinary project between computer scientists at LISN, economists at CREST and the French Public Employment Service to develop a job ad recommender system and assess its impact on the labor market. Beyond recommendation performance, we discuss issues such as privacy, fairness, congestion, and non-stationarity that arise in job recommendation and that must be handled with great care.
📄 Mixed precision iterative refinement for low-rank matrix and tensor approximations
Matthieu Robeyns (ParSys)
We present a new mixed precision algorithm to compute low-rank matrix and tensor approximations, a fundamental task in numerous applications in scientific computing and data analysis. Our algorithm is reminiscent of the iterative refinement framework for linear systems: we first compute a low-rank approximation in low precision and then refine its accuracy by iteratively updating it.
Using online algorithms for resource sharing
Valentin Dardilhac (GaLAC)
From the ski rental problem, which has known offline and online (with oracle) algorithms, we study several variants that should help us modelizing a network of data centers sharing resources, on which we try to minimize the number of communications so that the customers have a faster access to the required data. The talk will focus on offline algorithms (with all informations known), and online algorithms (with limited information), in which case we build approximation algorithms.