LIG Keynote Speeches

Les Grandes Conférences du LIG - The LIG Keynote Speeches
 - 
LIG
 -  19 février 2019

Algorithms for the Operation and Design of Bike-sharing Systems

David SHMOYS

Bike-sharing systems are changing the urban transportation landscape; for example, New York launched the largest bike-sharing system in North America in May 2013, and by 2017 there were roughly 17 million individual trips taken. We have worked with Citibike and their parent company Motivate, using analytics and optimization to change how they manage the system. Huge rush-hour usage imbalances the system - we answer the following two questions: where should bikes be at the start of a day and how can we mitigate the imbalances that develop?
We will survey the algorithmic tools we have employed for the former question, where we developed an approach based on continuous-time Markov chains combined with integer programming models to compute stocking levels for the bikes, as well as methods employed for optimizing (and re-optimizing) the capacity of the stations. For the question of mitigating the imbalances that result, we will describe both heuristic methods and approximation algorithms that guide both mid-rush hour and overnight rebalancing, as well as for the positioning of corrals, which have been one of the most effective means of creating adaptive capacity in the system. More recently, we have guided the development of Bike Angels, a program to incentivize users to crowdsource “rebalancing rides”, and we will describe its underlying analytics.

This is joint work with Daniel Freund, Shane Henderson, and Eoin O’Mahony, as well as Hangil Chung, Aaron Ferber, Nanjing Jian, Ashkan Nourozi-Fard, Alice Paul, and David Williamson.

Lire la suite
Les Grandes Conférences du LIG - The LIG Keynote Speeches
 - 
LIG
 -  07 février 2019

Trading off memory for bandwidth in a content-centric Internet

Jim ROBERTS

Some 96% of Internet traffic is currently generated by the transfer of digitized content, directly from content providers (CPs) like Netflix and Google, or via content delivery networks (CDNs) like Akamai and Limelite. In such a content-centric network there is clearly scope for significant economies in the cost of infrastructure by trading off memory for bandwidth. By retrieving popular content items from local storage, requirements for upstream bandwidth are greatly reduced. These economies are imperfectly realized in the current network where there is a mismatch between the objectives of network operators on one hand, and major CPs and CDNs on the other. The latter tend to jealously protect their profitable business models, notably by encrypting content delivery and thus preventing operators from transparently caching popular items at advantageous sites. They also have little incentive to cooperate in optimizing infrastructure costs through proactive placements, as long as their customers experience adequate quality. The talk will discuss how the Internet is likely to change to more effectively deal with its content-centric demand. Our analysis is based on mathematical models developed to determine cache hit rates accounting for observed characteristics of content popularity. These models enable a quantification of the memory for bandwidth tradeoff and an evaluation of alternative network structures. Our conclusion is that the future Internet will deliver the vast majority of content from datacenter-equipped central offices at the edge of the core network, or from caches located even closer to users in the access network. Most content delivery will still be controlled by major CPs and CDNs and we discuss how the network infrastructure owner will be able to persuade them to realize optimal placements through an appropriate pricing scheme.

Lire la suite
Les Grandes Conférences du LIG - The LIG Keynote Speeches
 - 
LIG
 -  10 janvier 2019

Privacy-preserving aggregation of data from multiple sources

David POINTCHEVAL

Gigabits of data are regularly aggregated in order to deliver statistics and recommendations, or even to make decisions. These data are processed in clear by many providers that offer valuable services, but at the cost of a huge risk with respect to privacy. The providers themselves or even hackers could exploit these data for malicious purposes. Privacy-by-design would be preferable.
Cryptography has recently developed new tools in order to allow aggregation on encrypted data, with fully homomorphic encryption and functional encryption. However, whereas they work well for one user, they fail to aggregate data that come from different sources, in particular when these sources do not trust each other.
In this talk, we will present new techniques of aggregation for data that come from multiple mutually distrustful sources, so that privacy is guaranteed, and the data owners keep control on the performed aggregation.

Lire la suite
Les Grandes Conférences du LIG - The LIG Keynote Speeches
 - 
LIG
 -  08 novembre 2018

40 years of static analysis of numerical programs

Nicolas HALBWACHS

Static analysis of programs consists in extracting guaranteed properties about all executions of a program without executing it. Such properties are useful in compilation, verification, optimization and evaluation of programs. Abstract interpretation, introduced by Patrick and Radhia Cousot in the late seventies, is the theoretical framework of static analysis. In this talk, we will focus on static analysis of numerical properties, like variable boundedness or more general invariant relations between numerical variables. During the last decades, such analyses have been widely studied, in view of finding a compromise between the expressiveness of considered properties and the cost of the analysis. We will try to summarise these works together with their main applications.

Lire la suite
Les Grandes Conférences du LIG - The LIG Keynote Speeches
 - 
LIG
 -  04 octobre 2018

Majority judgment: Why it should be used to rank and elect

Rida LARAKI

Every well-known voting system in use today hides important vices that can deny the will of the electorate including majority vote with only two candidates (the domination paradox), approval voting, all methods that ask voters to compare candidates (i.e., rank-order them), and point-summing methods. The underlying reason: the inability of voters to adequately and honestly express their opinions. Majority judgment asks voters to evaluate every candidate in an easily understood common language of ordinal grades such as: Great, Good, Average, Poor, or Terrible. Majorities determine the electorate’s evaluation of each candidate and the ranking between every pair of candidates (necessarily transitive), with the first-placed among them the winner.

Lire la suite
Les Grandes Conférences du LIG - The LIG Keynote Speeches
 - 
LIG
 -  07 juin 2018

The Cognitive Packet Network - Reinforcement based Network Routing with Random Neural Networks

Erol GELENBE

The Cognitive Packet Network (CPN) is an experimental network routing protocol which uses specific Quality of Service (QoS) objectives incorporated in a Goal Function, together with network measurement by Smart Packets (SPs). It updates neural network based Oracles in routers using Reinforcement Learning, in order to dynamically select network paths so that end users can convey their payload traffic with a performance that matches the Goal as closely as possible. The Goal can include conventional QoS metrics such as delay and loss, as well as Real-Time objectives, as well as newer metrics of interest including Energy Consumption and Security. Payload traffic is forwarded using source or segment routing, selected through the reinforcement learning approach, while SPs conduct their exploration using a node by node process by seeking the best direction from each Oracle. CPN has been implemented in various contexts: on 10-40 node test-beds, on an intercontinental scale as an overlay network, within SDN routers, and as a means to convey task requests over the Internet to Cloud servers. Our presentation will detail the CPN algorithm and the Random Neural Networks that are used to implement the Oracles. We will also present relate experimental measurements and results. The work has appeared in a variety of journals and conferences including CACM, Proceedings IEEE, IEEE J. Sel. Areas in Comms.

Lire la suite
Les Grandes Conférences du LIG - The LIG Keynote Speeches
 - 
LIG
 -  03 mai 2018

Reasoning on Data: Challenges and Applications

Marie-Christine ROUSSET

How to exploit knowledge to make better use of data is a timely issue at the crossroad of knowledge representation and reasoning, data management, and the semantic web.

Knowledge representation is emblematic of the symbolic approach of  Artificial Intelligence based on the development of explicit logic-based models processed by generic  reasoning algorithms that  are founded in logic. Recently, ontologies have evolved in computer science as computational artefacts to provide computer systems with a conceptual yet computational model of a particular domain of interest. Similarly to humans, computer systems can then base decisions on reasoning about domain knowledge. And humans can express their data analysis needs using terms of a shared vocabulary in their domain of interest or of expertise.

In this talk, I will show how reasoning on data can help to solve in a principled way several problems raised by modern data-centered applications in which data may be  ubiquitous, multi-form, multi-source and musti-scale. I will also show how knowlege representation formalisms and reasoning algorithms have evolved to face scalability issues and data quality challenges.

Lire la suite
Les Grandes Conférences du LIG - The LIG Keynote Speeches
 - 
LIG
 -  05 avril 2018

Issues in Ethical Data Management

Serge ABITEBOUL
Lire la suite
Les Grandes Conférences du LIG - The LIG Keynote Speeches
 - 
LIG
 -  05 avril 2018

On Turning Domain Knowledge into Tools

Jean-Marc JÉZÉQUEL

One of the biggest challenges of the digital age is to turn human knowledge, know-how and procedures into software. When the domain of expertise is close enough to computer science, software engineers typically can manage it because they can understand the full spectrum of the problems, ranging from the problem domain (how to do the right thing) to the solution space in the computer (how to do the thing right).

However, when the domain stands far away from the software engineer's expertise, it is much more difficult to do the right thing. A lot of approaches have been developed over the years to handle this gap. In this talk we reflect on one of these approaches, based on the idea of using models to capture domain knowledge at the right level of abstraction, and software tools to transform these models into technical solutions. In this paradigm, the mission of software engineers becomes providing the domain experts with the right tool-supported modeling languages that is, turning domain knowledge into tools.

Lire la suite
Les Grandes Conférences du LIG - The LIG Keynote Speeches
 - 
LIG
 -  05 avril 2018

Human-Computer Interaction: Back to the future and... forward to the past

Stéphane HUOT

Long before personal computers, the Internet and smartphones, Human-Computer Interaction (HCI) was already at the heart of some of the visions that have shaped modern computing. But for years, priority has mostly been put on intrinsic power and development of features rather than how to use them. The popularization of digital devices such as smartphones, tablets or gaming consoles slowly reversed this trend and the argument of simplicity of use has replaced that of the intrinsic power. But it also led to a relative impoverishment of the possibilities offered by technologies that are paradoxically more powerful than ever. By hiding complexity rather than helping to master it, by keeping the myth alive that such devices make it possible to do a lot without efforts, the trend is now to sacrifice empowerment of users for simplicity of use.

Lire la suite

Pages