Séminaires ED d’Informatiques 2019-2020

Dates

  • Jeudi 10 Octobre 2019 : Manel Ayadi + Alexandre ARAUJO Salle A304
  • Jeudi 7 Novembre 2019 : Eric Benamou + Raphael Pinot Salle P507
  • Jeudi 19 Décembre 2019 : Alexis Duburcq+ Guillaume Prévost Salle P517
  • Jeudi 16 Janvier 2020 : Amin Farvardin + () Salle P517
  • Jeudi 13 Février 2020 : Raja Trabelsi + Felippe Garrido Salle P517
  • Jeudi 12 Mars 2020 : Hajer Ben Fekih + Ons Nefla Salle P517
  • Jeudi 09 Avril 2020 : Pedro Guillermo Lopez+ Beatrice Napolitano Salle P517
  • Jeudi 14 Mai 2020 : Geovani Rizk+ Beji Celine Salle P517
  • Jeudi 18 Juin 2020 : Axel Faure Beaulieu + () Salle P517

 

COURS 1 (Octobre – 2019, Prof invité)

Titre : Automated Reasoning for Social Choice Theory
Intervenants : Ulle Endriss
Volume horaire : 9h, 3 fois 3h, sur deux Mardi
Dates : Mardi 1 Octobre: 6h. Matin 9h-12h. Après Midi 14h-17h (B510)
Mardi 8 Octobre: 3h Après midi: 14h-17h. (C108)

Description: One of the most exciting development in computational social choice in recent years has been the use of tools for automated reasoning developed in AI, notably SAT solvers, to support researchers in social choice theory in their quest of getting a deeper understanding of the axiomatic foundations of collective decision making.

This short course, based on the course on computational social choice I teach at the ILLC in Amsterdam (http://www.illc.uva.nl/~ulle/teaching/comsoc/2019/) will enable participants to employ these tools in their own research. Lectures will cover both introductory material on the axiomatic method in social choice theory and a hands-on session on how to use a modern SAT solver to (partly) automate the proof of the seminal Gibbard-Satterthwaite Theorem. Besides attending lectures, participants will complete a programming assignment and present a recent paper from the relevant literature. The course is equally suitable for those carrying out research in (computational) social choice themselves and those who are new to the field.

The only prerequisites for being able to fully benefit from the course are some basic programming skills in Python and familiarity with classical propositional (boolean) logic.

COURS 2 (Octobre 2019, Prof Invité)

Titre : Judgement Aggregation and Strategy-Proof Social Choice
Intervenants : Clemens Puppe
Volume horaire : 6h le Mercredi et Jeudi de14h à 17h.
Dates : Mercredi 9 Octobre: 3h Après midi, 14h-17h. (P521)
Jeudi 10 Octobre, 3h Après midi, 14h-17h (Salle C bis)

Description : We review the basic results in the recent field of judgement aggregation and explore some deep connections with the theory of strategyproof social choice on restricted domains. At the heart of the course is the characterization of all monotonic, issue-wise aggregation rules in terms of the Intersection Property (Nehring and Puppe, Journal of Economic Theory 2007).

COURS 3 (Octobre 2019, Prof invité)

Titre : Byzantine Fault Tolerant Distributed Computing
Intervenants : Aris Pagourtzis
Volume horaire : 3h Mardi.
Dates : Mardi 15 Octobre, 14h-17h. (Salle C)

Description : Byzantine Fault Tolerance (BFT) is a fundamental issue in distributed computing, which has recently received renewed attention due to the advent of the blockchain technology and its potential application in a vast number of distributed systems. We will study BFT issues in both main paradigms of distributed computing, namely message passing and mobile agents. Regarding the former, we will talk about the reliable broadcast problem, also known as Byzantine Generals. For the latter, we will focus on exploration and rendezvous by mobile agents in the presence of malicious agents. We will present earlier and recent results for several problems and settings in these two exciting areas of research.

COURS 4 (Octobre, Novembre 2019, Prof invité)

Title: Introduction to Computational Social Choice
Intervenants : Piotr Skowron
Volume horaire : 12h, les jeudi.
Dates : Jeudi, 14h-17h, 31 October (C108), 7th November (C127), 14 November, 21 November

Description : The objective Computational social choice is a field at the intersection of economics (specifically, the social choice theory), mathematics and computer science. It studies situations where a group of agents needs to reach a collective decision, but the agents might have conflicting preferences with respect to the decision to be made. In particular, it analyses tools that facilitate such decisionmaking, aims at comparing the quality and suitability of such tools, and studies computational problems that arise in the process of making a decision. A particular example of such tools are voting rules---functions that take agents' preferences as input (the preferences can be represented in various ways) and return an outcome. The voting rules can be used to select a single winner among a group of candidates, to provide a ranking of candidates (e.g., contestants in a competition), to select a bunch of projects that a city council should fund (participatory budgeting), etc.
In this course we will cover selected topics from computational social choice, specifically focussing on the following question: "How computer science and discrete mathematics can help in understanding and comparing voting rules?".
During the course, we will define and explain a number of voting rules, we will introduce the classic axiomatic approach that consists in formulating certain desired properties that voting rules should satisfy and examining which voting rules satisfy them (we will explain how this axiomatic approach can be enhanced by using computers, specifically SAT solvers), we will explain the utilitarian approach to comparing voting rules (in particular, showing how the idea of approximation algorithms can be used to better understand the suitability and to assess the quality of decision rules), we will analyse the computational complexity of finding outcomes of certain voting rules and related computational problems.

The course will be based on the following resources:

[1] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia: Handbook of Computational Social Choice. Cambridge University Press 2016.

[2] Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon: Multiwinner voting: A new challenge for social choice theory. In Ulle Endriss, ed., Trends in Computational Social Choice. AI Access Foundation 2017.

[3] Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, Piotr Skowron: Approximating optimal social choice under metric preferences. Artificial Intelligence 264: 27-51, 2018.

COURS 5 (Janvier, Février 2020)

Titre : Introduction du algorithmic game theory
Intervenant : Laurent Gourves
Volume horaire : 18h, les jeudi.
Dates : Jeudi, 14h-17h, 9 Janvier, 16 Janvier, 23 Janvier, 30 Janvier, 6 février, 27 Février (Salle A 407)

Description :The objective: Introduction to (mostly strategic) games and discrete optimization problems. Solution concepts: definition, algorithmic construction, quality (price of anarchy and stability). Games of potential/congestion games. Auctions, stable marriage.

Références :

Algorithmic game theory, Tardos Roughgarden, Vazirani (ed), Cambridge university press, 2007.

Networks, Crowd, and Markets: reasoning about a highly connected world. Easley & Kleinberg, Cambridge university press, 2010.

20 Lectures on Algorithmic game theory, Roughgarden, Cambridge university press, 2016

COURS 6 (Mars, Avril 2020)

Titre : Polynomial and Super-polynomial Approximation of NP-hard problems
Intervenant : Vangelis Paschos
Volume horaire : 18h, les jeudi.
Dates : Jeudi, 14h-17h, 5 Mars, 12 Mars, 19 Mars, 26 Mars, 2 Avril, 23 Avril (Salle A 407)

The objective: A graduate course for the students of LAMSADE/CEREMADE. Polynomial approximation of NP-hard problems in one of the first Theoretical Computer Science and Complexity Theory research topics born two years after the first NP-completeness proof of SAT. The objective of of polynomial approximation is to design polynomial algorithms for NP-hard problems computing solutions the values of which is, in worst case as close to optimal solution as possible for any instance of the problem studied. The measure of such closeness is the so-called approximation ratio. Super-polynomial approximation is a recent research program mainly developed in LAMSADE in order to remedy to the negative results proved in the framework of polynomial approximation for the quasi-totality of the paradigmatic combinatorial optimization problems. Here the objective is to develop exponential algorithms guaranteeing approximation ratios impossible in polynomial time, these algorithms having an exponential worst case complexity much than the best known exact complexity of the optimal algorithms for problems tackled.

References

M. R. Garey, D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W. H. Freeman 1979

C. H. Papadimitriou, K. Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice Halln, 1981

V. Th. Paschos, Complexité et approximation polynomiale Hermès, 2004

COURS 7 (Juin 2020, Prof invité)

Title: Parameterized Complexity or Kernelization (a subarea in parameterized complexity)
Intervenants : Venkatesh Raman
Volume horaire : 12h, les Mardi et Jeudi.
Dates : Mardi 16 Juin et Jeudi 18 Juin de 14h-17h , Mardi 23 Juin et Jeudi 25 Juin: 14h-17h (Salle A 407)

The objective: I hope to cover algorithmic techniques and lower bounds. Exact topic can be based on the interest of the participants.