What is makushita?
- 1) Makushita is the third division of sumotori competitions.
- 2) This is a seminar made by non-permanent (ie PhD students, interns, post doc...) members of SUMO and LOGICA teams whose goals are to allow discussion within the teams, know better each other's subject and present new results or work in progress.
List of Makushita seminars: (clic for slides!)
September 17, Suman Sadhukhan: Network Games with Synchronous Cost
Network games are multi-player, concurrent, non-zero sum games on a directed graph, and in most cases one-shot variants. Each player selects a path from source to target on the game graph ("selfish" behavior), pays cost, bears positive or negative congestion effect (i.e, shares or pays more) depending on the setting. Unlike one-shot selection of the whole path, we define our model where players' paths get affected by how other players are playing. Our model also departs from most of the classical models in the way of computing the cost of a player: in our model a player shares cost/ suffer congestion with another player only when their path intersect at some step, i.e, synchronize at their intersection, unlike only having intersection of chosen path but possibly taken at different step. We call this setting as Network games with synchronous cost. We study how "selfish" behavior affects on the total cost/payoff compared to a centralized setting in this model: how players achieve an Equilibrium, what measures like Price of Anarchy (PoA), Price of Stability (PoS) turn out to be, to precisely compare these two behaviors. Different models for different applicability have been studied in this line of research, where most of the studies talk about bounds of PoA, PoS in their respective models. Here we have studied how to compute those for a particular instance of our model. We provide EXPTIME algorithms to precisely compute PoS and PoA for an instance.
July 16, Pierre Boudart: Model of a railway network
We consider the optimal regulation problem for a railway network. We provide a model to study the traffic and the different possible choices. The model is compact and clearly shows the impacts of the choices.
July 9, Mathieu Poirier: Process discovery using Petri Net synthesis.
In this presentation we see why Petri nets are a good model for processes and how their synthesis from logs allow to address the problem of process discovery. Further work about outlier detection in the logs and synthesis to a net with a lower size are mentioned.
July 2, Graeme Zinck: Enforcing opacity in modular systems.
With the prevalence of online services with many interacting components, we need ways of ensuring these modular systems are secure. By modelling these services as finite state automata, we can check that secrets are never leaked using the notion of opacity. We present optimized techniques for verifying and enforcing opacity in modular systems.
June 25, Emily Clement: Differential privacy and personalized differential privacy.
Privacy is a big isssue. It is important to provide guarantees for personnal data when proceeding to their analysis. Different models have been proposed to ensure levels of data privacy. One of the issues of these models is the level of privacy. What if users do not require the same level of privacy? We will explain this issue with the Personnalized Differential Privacy.
June 18, Hugo Bazille: Classi cation among Hidden Markov Models.
Given two systems A1, A2 and an observation w, we would like to be able to decide which system produced this observation, that is to classify among two systems. In this talk, we present classification on some stochastic model: Hidden Markov Models. We present some complexity results about classification for attackers with different powers.
June 11, Leo Henry: Optimal test case generation using game theory.
Ongoing works and hopes around model based timed testing using timed automata.
June 04, Tristan Charrier: Dynamic epistemic logic with probabilities.
In this talk, we present a logic for reasoning about knowledge, dynamic and probabilities. We discuss ongoing work on a formalization using dynamic epistemic logic with probabilities, detail its definition and show examples.
May 21, Bastien Thomas: Automated Verification of Randomised Distributed Algorithms.
Randomised distributed algorithms appear naturally in consensus-related problem where the famous impossibility theorem of Fisher, Lynch and Paterson apply. However, these algorithms exhibit complex behaviours that are hard to describe exhaustively in a pen and paper proof. In this presentation, we use model-checking to propose a method for verifying parametrised properties on such algorithm, allowing us notably to verify algorithms for every possible number of processes at once.
May 06, Adrian Puerto-Aubel: Speed up for quantum algorithms.
We present the basic concepts of quantum computing. Starting from the elementary quantum data unit, the qbit, we explain the treatment of qbit registers, and the operations one can perform on them, or reversible gates.
This makes a strong analogy with digital circuits, and we present the way these are used for quantum programming, with a special focus on the online tool from IBM.
Finally, we roughly explain the advantages of quantum over classical computing, with an overlook on the source of the speedup, and we introduce the class of problems for which this speedup is qualitative.