Computer Science Seminars

Université Libre de Bruxelles

Computer Science Department

November 9th 2022 at 12:15 - Solvay Room

Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds

We consider the unlabeled motion-planning problem of m unit-disc robots moving in a simple polygonal workspace of n edges. The goal is to find a motion plan that moves the robots to a given set of m target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end. If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time O(nlog n + mn + m^2) if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance 4 apart, any two target positions are at least distance 4 apart, and any pair of a start and a target positions is at least distance 3 apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary.

Irina Kostitsyna is an assistant professor in the Applied Geometric Algorithms group in the Department of Mathematics and Computer Science. Her research interests lie in the field of computational geometry, both in its theoretical and applied aspects. In particular, her main topics of research include geometric algorithms for mobile agents, including path planning and routing; and for programmable matter, including shape reconfiguration problems.

December 2nd 2022 at 12:15 - Forum F

Deliveries with cargo-bike and robot

Planning last-mile delivery operations is one of the most crucial tasks faced by e-commerce companies. If last-mile delivery is carefully designed, not only can customers' expectations be fulfilled, but also urban congestion and noxious emissions can be addressed. However, a smart planning of last-mile delivery operations is particularly challenging because e-commerce companies can rely on razor-thin marginal profits. E-commerce giants, such as Amazon or JD.com, are investigating new paradigms to run last-mile deliveries. One of the most promising ways to improve the current practices in last-mile delivery is to adopt Unmanned Autonomous Vehicles (UAV), such as drones or self-driving robots. UAVs complement or replace conventional vehicles, such as vans or cargo-bikes. In this talk we consider deliveries made by a deliveryman that rides a cargo-bike helped by a self-driving robot. The bike and the robot leave together a central depot and deliver a number of packages. When the robot is empty it can be replenished by the deliveryman. This implies that the robot and the bike might meet during the working shift. When delivery operations are finished, the deliveryman and the robot go back to the depot. We formally describe and formulate the problem with two Mixed-Integer Linear Programming (MILP) models. The first model is a compact MILP featuring a polynomial number of variables and constraints. The second MILP builds upon the first model but features an exponential number of constraints. We also propose a set of valid inequalities to tighten the linear relaxation of both these MILP models and embed these cuts into branch-and-cut algorithms. We present a genetic algorithm, based on dynamic programming recursions to explore a large neighborhood of solutions and to find high-quality primal solutions of the problem. We test the proposed branch-and-cut algorithms and the genetic algorithm on real-life instances provided by JD.com and show that the branch-and-cut methods can find optimal solutions of most of the proposed instances with up to 80 customers. This work is in collaboration with Ningxuan Kang, Roberto Roberti and Yanlu Zhao

October 27th 2022 at 11:00 - Solvay Room (NO building, 5th floor)

Collective Learning Dynamics

Artificial intelligence research makes the decision-making capabilities of autonomous agents increasingly powerful, using the technique of reinforcement learning. However, little is known about the collective behavior that emerges from and influences a set of multiple reinforcement learning agents. To this end, I present how to efficiently describe the emergent behavior of reinforcement learning agents via dynamical systems theory. The proposed approach has the potential to become a practical, lightweight, and robust tool to create insights about collective learning in uncertain and changing environments.

Wolfram Barfuss is a research scientist at the Tübingen AI Center at the University of Tübingen in Germany. He studied physics (M.Sc. 2015), focusing on complex systems at the University of Erlangen-Nuremberg and University College London. In 2019, he received a doctorate in natural science from the Humboldt University Berlin for his work on learning dynamics and decision paradigms in social-ecological dilemmas. Before joining the University of Tübingen, he was a research fellow in the School of Mathematics at the University of Leeds, the Max Planck Institute for Mathematics in the Sciences in Leipzig, and held guest research appointments at the Stockholm Resilience Centre and Princeton University.

April 21th 2022 at 12:15 - Solvay Room (NO building, 5th floor)

Post-Quantum Cryptography: maintaining security in a quantum world

Jan-Pieter D'Anvers

Quantum computers are predicted to break our current (public key) encryption and signature standards, which are based on factoring. To protect our data and devices in a future with quantum computing, a paradigm shift towards new types of cryptography is needed. Such new algorithms, secure against quantum computers, are developed in the field of post-quantum cryptography. In this talk we will look at new quantum-safe (or post-quantum) algorithms that are designed to replace the insecure old standards. The goal is to get an idea of how these algorithms work and what challenges lie ahead in the implementation and deployment of these standards.

Jan-Pieter D'Anvers is a postdoctoral researcher in the COSIC research group from KU Leuven. His research focuses on the design, security and side-channel security of post-quantum cryptography (i.e. cryptography that is secure in the presence of quantum computers) and fully homomorphic encryption (i.e. encryption that allows computation on the encrypted data). He is co-designer of Saber, one of the final candidates in the NIST post-quantum standardization process, an international standardization effort.

April 27th 2022 at 12:15 - Room P.Forum.F

Proximity-based authentication: Secure realisation of distance bounding protocols

Relay attacks pose an important threat in wireless ranging and authentication systems. Distance bounding protocols have been proposed as an effective countermeasure against relay attacks and allow a verifier and a prover to establish an upper bound on the distance between them. In this talk, we will discuss why distance bounding protocols are an interesting security primitive, but also why these protocols are difficult to realise in practice. Next, we will present several design approaches for the secure realisation of distance bounding protocols which have been recently proposed in the literature.

Dr. Ir. Dave Singelée received the Master’s degree of Electrical Engineering and a PhD in Applied Sciences in 2002 and 2008 respectively, both from the KU Leuven (Belgium). He worked as an ICT security consultant at PricewaterhouseCoopers Belgium, and is currently an industrial research manager (IOF) at the research group COSIC. His main research interests are cryptography, security and privacy of wireless communication networks, key management, distance bounding and cryptographic authentication protocols, and security solutions for medical devices.

March 31th 2022 at Noon - Location S.R42.4.502

**Note Location on Solbosch!!**

Learning multidirectional functional models with MERCS

March 24th 2022 at Noon - Solvay Room (5th Floor NO building)

The algorithmic challenges of local fast re-routing

The dependability of distributed systems often critically depends on the underlying communication network, realized by a set of routers. To provide high availability, modern routers support local fast rerouting of flows: routers can be preconfigured with conditional failover rules which define to which port a packet arriving on this incoming port should be forwarded deterministically depending on the status of the incident links only. As routers need to react quickly, they do not have time to learn about remote failures. My talk revolves around the fundamental question whether and how local fast rerouting mechanisms can be configured such that packets always reach their destination even in the presence of multiple failures, as long as the underlying network is still connected. I will show that this algorithmic problem is related to the field of disconnected cooperation, and offers a number of challenging research questions -- and sometimes surprising results. In particular, I will give an overview of state-of-the-art algorithmic techniques for different realistic graph classes (from dense datacenter topologies to sparse wide-area networks) and discuss lower bounds and impossibility results. While the main focus of the talk will be on deterministic algorithms, we will also take a glimpse at the power of randomization.

Stefan Schmid is a Full Professor at the Technical University of Berlin, Germany, working part-time for the Fraunhofer Institute for Secure Information Technology (SIT). MSc and Ph.D. at ETH Zurich, Postdoc at TU Munich and the University of Paderborn, Senior Research Scientist at T-Labs in Berlin, Associate Professor at Aalborg University, Denmark, and Full Professor at the University of Vienna, Austria. Stefan Schmid received the IEEE Communications Society ITC Early Career Award 2016 and an ERC Consolidator Grant 2019. His current research interests revolve around the fundamental and algorithmic problems arising in networked systems.

March 11th 2022 at 12:15-13:15 (NOTE CHANGE FROM 12:00) - Solvay Room (5th Floor NO building)

Cryptographic protocols in the real world

Jens Hermans

Nextauth

Nextauth

March 2nd 2022 at Noon - Forum A

Rectilinear convex hull of points in 3D

February 8th 2022 at Noon - OF2072-2074

The Balanced Minimum Evolution Problem (BMEP) is a NP-hard network design problem that consists of finding a minimum length unrooted binary tree (also called a phylogeny) having as a leaf-set a specific set of items encoding molecular sequences. The optimal solution to the BMEP (i.e., the optimal phylogeny) encodes the hierarchical evolutionary relationships of the input sequences. This information is crucial for a multitude of research fields, ranging from systematics to medical research, passing through drug discovery, epidemiology, ecology, biodiversity assessment and population dynamics. In this talk, we introduce the attendant to the problem and its applications as well as to its connections with other areas such as data compression and information entropy. We review the most important results achieved so far and the challenges that still remain to be addressed.

Friday November 26th 2021 at 12:15 PM - Solvay Room (5th Floor NO building)

The impact of social perception biases in collective action dynamics

Fernando P. Santos

Assistant Professor at Informatics Institute, University of Amsterdam. Socially Intelligent Artificial Systems and Civic AI Lab

Assistant Professor at Informatics Institute, University of Amsterdam. Socially Intelligent Artificial Systems and Civic AI Lab

When individuals face collective action problems, their expectations about the current and future behavior of others are fundamental to trigger cooperation. There is a catch, however: in the context of global public goods games, it can be hard to perceive the overall behaviors of others, and, in fact, individuals often incur social perception biases — i.e., over- or under-estimating the actual cooperation levels in a population. One pressing domain where such biases can have an impact is climate change, as people typically underestimate the pro-climate positions of others. To design incentives that enable cooperation and a sustainable future one must consider how social perception biases affect collective action. In this talk, I will discuss a theoretical model — based on game theory and best-response learning dynamics — that allows us to investigate the effect of social perception bias in (non-linear) public goods games. We will see that different types of bias play a distinct role in cooperation dynamics. False uniqueness (underestimating own views) and false consensus (overestimating own views) can both explain why communities get locked in suboptimal states. Furthermore, we will discuss how biases also impact the effectiveness of typical monetary incentives, such as fees. This will allow us to discuss, finally, how targeting biases, e.g., by changing the information available to individuals, can comprise a fundamental mechanism to prompt collective action.

Friday November 5th 2021 at 12:15 PM - Solvay Room (5th Floor NO building)

Many discrete optimization problems amount to select a feasible subgraph of least weight. We consider in this paper the context of spatial graphs where the positions of the vertices are uncertain and belong to known uncertainty sets. The objective is to minimize the sum of the distances in the chosen subgraph for the worst positions of the vertices in their uncertainty sets. We first prove that these problems are NP-hard even when the feasible subgraphs consist either of all spanning trees or of all s-t paths. In view of this, we propose en exact solution algorithm combining integer programming formulations with a cutting plane algorithm, identifying the cases where the separation problem can be solved efficiently. We also propose two types of polynomial-time approximation algorithms. The first one relies on solving a nominal counterpart of the problem considering pairwise worst-case distances. We study in details the resulting approximation ratio, which depends on the structure of the metric space and of the feasible subgraphs. The second algorithm considers the special case of s-t paths and leads to a fully-polynomial time approximation scheme. Our algorithms are numerically illustrated on a subway network design problem and a facility location problem.

Michaël Poss graduated in Mathematics from the Université Libre de Bruxelles, and in Operational Research from the University of Edinburgh. His thesis was done at the GOM research group from the Université Libre de Bruxelles, under the supervision of Bernard Fortz, Martine Labbé, and François Louveaux. During my PhD, he spent time in Rio de Janeiro, working at the Universidade Federal do Rio de Janeiro and at the CEPEL, working with Claudia Sagastizabal and Luciano Moulin. After his thesis was defended in Feburary 2011, he spent a couple of months at the Universidade de Aveiro, followed by a postdoctoral stay at the CMUC from the Universidade de Coimbra. He was a CNRS researcher at Heudiasyc from October 2012 to January 2015 and joined the LIRMM in February 2015. He has been a senior researcher (directeur de recherche) since 2020.

Friday October 8th 2021 at 12:15 PM - Forum E

Connected cops and robbers games : related width parameters, structural results and algorithms

Christophe Paul

ALgorithms for Graphs and COmbinatorics group (AlGco) of the LIRMM

ALgorithms for Graphs and COmbinatorics group (AlGco) of the LIRMM

A cops and robber game, or a search game, consists in locating an intruder (the robber) by placing and moving searchers (the cops) on the vertices of the graph. An edge is cleaned when its two vertices are simultaneously occupied by searchers. A search strategy is monotone if no edge recontamination is permitted. It is well known that depending on the ability of the intruder, laziness or agileness, the numbers of required searchers to clean the graph (with a monotone strayegy) respectively corresponds to the treewidth and pathwidth parameters. In this talk, we will consider the connected variant of these search games, where the clean territory is required to be connected. It is known that a monotone search against an agile intruder, satisfying connectivity constraint requires to double the number of searchers. The connected search number against an agile intruder defines the connected pathwidth parameter. Recently, it has been proved that for every fixed k, deciding whether the connected pathwidth of a graph is at most k is polynomial time solvable (belongs to the complexity the class XP). We will sketch a fixed parameter (FPT) algorithm for that problem. Beside connected pathwidth, one can define the connected treewidth by considering a connected search against a lazy intruder. It turns out that in this case the price of connectivity is unbounded. We can show that even for series-parallel graphs (aka treewidth 2 graphs), the connected search number can be arbitrarily large (see figure). One can observe that connected pathwidth and connected treewidth are not closed undertone minor relation but are closed under edge contraction. We show that for every k at least 2, the number of (contraction) obstructions is infinite and we will provide a full (and finite) description of the obstruction set for k=2. We let open the question whether deciding the connected treewidth is fixed parameter tractable, but (depending on the time) we will describe a polynomial time algorithm for series-parallel graphs.

Christophe Paul is a a full-time researcher at the CNRS, with the ALgorithms for Graphs and COmbinatorics group (AlGco) of the LIRMM. His research focusses on graph theory and algorithms and more specifically on graph decomposition techniques, combinatorial algorithms and fixed parameterized algorithms. He also has interests in computational complexity, combinatorics, computational biology and many others in computer science and discrete mathematics

February 10th, 2020, 12:30 PM - Solvay Room (NO5)

Fare Evasion in Transit Networks

Jannik Matuschke

Research Center for Operations Management, KU Leuven

Research Center for Operations Management, KU Leuven

Fare evasion in transit networks causes significant losses to the operators. In order to decrease evasion rates and reduce these losses, transportation companies conduct fare inspections to check traveling passengers for valid tickets. In this talk, we will discuss a bilevel optimization model for distributing such inspections in the network while taking into account the passengers' reaction. We will report on theoretical insights, a resulting collaboration with transportation authorities, and give an outlook on future research.

Jannik Matuschke is an Assistant Professor of Operations Management at KU Leuven. Before joining KU Leuven in 2019, he was a lecturer in Operations Research at Technische Universität München. Earlier, he was a postdoc at Universidad de Chile and a visiting professor at the University of Rome "Tor Vergata". He obtained his PhD in Mathematics at TU Berlin in 2013. Jannik's research focusses on combinatorial optimization and graph algorithms, in particular network and scheduling problems, approximation algorithms, and applications in logistics and transportation.

May 24th, 2019, 4:00 PM, room: NO906

Diameter computations in graphs and shortest paths problems

Michel Habib
(Université de Paris)

Computing the diameter of a graph (maximum number of edges on a shortest path) is a fundamental graph problem with countless applications in computer science and beyond.
Unfortunately, the textbook algorithm for computing the diameter of an *n*-vertex *m*-edge graph takes *O(nm)*-time.
This quadratic running-time is too prohibitive for large graphs with millions of nodes.

The radius and diameter of a graph are part of the basic global parameters that allow to apprehend the structure of a practical graph. More broadly, the eccentricity of each node, defined as the furthest distance from the node, is also of interest as a classical centrality measure. It is tightly related to radius which is the minimum eccentricity and to diameter which is the maximum eccentricity.

On the one hand, efficient computation of such parameters is still theoretically challenging as truly sub-quadratic algorithms would improve the state of the art for other ``hard in P'' related problems such as finding two orthogonal vectors in a set of vectors or testing if one set in a collection is a hitting set for another collection. A sub-quadratic diameter algorithm would also refute the strong exponential time hypothesis (SETH) and would improve the state of the art of SAT solvers. I will explain the reduction between deciding if the diameter of a split graph is 2 or 3 and a subexponential algorithm for SAT. Then I will propose a kind of dichotomy result for split graphs trying to fix the boarder between linear and quadratic algorithms.

On the other hand, a line of practical algorithms has been proposed based on performing selected Breadth First Search traversals (BFS) allowing to compute the diameter of very large graphs. However, such practical efficiency is still not well understood. We propose a notion of certificate that helps to capture the efficiency of these practical algorithms.

I will finish with a survey of the practical algorithms that compute shortest paths in road networks and some open problems involving dynamic networks.

Michel Habib is professor emeritus in Computer Science at University Paris Diderot - Paris 7, UFR d’Informatique.
He is a member of both the research group *Algorithms and discrete structures* and the INRIA Paris research team *Gang*.
His research is mainly focused on classic algorithms on discrete structures with special interest for graphs and orders, including:

- Well structured classes of graphs and orders
- Graph decompositions with special interest to modular decomposition
- Graph searching with special interest to LexBFS (Lexicographic Breadth First Search) and LexDFS (Lexicographic Depth First Search)
- Applications to biology (Phylogeny and Networks analysis)
- Practical Algorithms for huge graphs
- Algorithms for finding regularities in huge graphs

The speaker is hosted by Jean-Paul Doignon.

Distinguished seminar

May 23th, 2019, 12:30 PM, room: Forum F

Location Information

Maarten Löffler
(Utrecht University)

Let P be a set of n points in the plane. In the traditional geometric algorithms view, P is given as an unordered sequence of **locations** (usually pairs of x and y coordinates). There are many interesting and useful structures that one can build on top of P: the Delaunay triangulation, Voronoi diagram, well-separated pair decomposition, quadtree, etc. These structures can all be represented in O(n) space but take Omega(n log n) time to construct on a Real RAM, and, hence, contain information about P that is encoded in P but cannot be directly read from P.

In this talk I will explore the question how much information about the structure of a set of points can be derived from their locations, especially when we are *uncertain* about the locations of the points.

Maarten Löffler is currently an assistant professor at Utrecht University. He has been a post-doc researcher at the Bren School of information and computer sciences of the University of California, Irvine. He was a PhD-student at Utrecht University.

The speaker is hosted by the Algorithms Group.

March 29th, 2019, 3:00 PM, room: Forum C

Real-Time Data Mining

Nowadays, there are applications in which the data are modelled best not as persistent tables, but rather as transient data streams. In this keynote, we discuss the limitations of current machine learning and data mining algorithms. We discuss the fundamental issues in learning in dynamic environments like learning decision models that evolve over time, learning and forgetting, concept drift and change detection. Data streams are characterized by huge amounts of data that introduce new constraints in the design of learning algorithms: limited computational resources in terms of memory, processing time and CPU power. In this talk, we present some illustrative algorithms designed to taking these constrains into account. We identify the main issues and current challenges that emerge in learning from data streams, and present open research lines for further developments.

João Gama is an Associate Professor at the University of Porto, Portugal. He is a senior researcher and member of the board of directors of the LIAAD, a group belonging to INESC Porto. He is Director of the master Data Analytics. He serves as member of the Editorial Board of MLJ, DAMI, TKDE, NGC, KAIS, and IDA. He served as Chair of ECMLPKDD 2005 and 2015, DS09, ADMA09 and a series of Workshops on KDDS and Knowledge Discovery from Sensor Data with ACM SIGKDD. His main research interest is in knowledge discovery from data streams and evolving data. He is the author of a recent book on Knowledge Discovery from Data Streams. He has extensive publications in the area of data stream learning.

The speaker is hosted by the Machine Learning Group.

Thursday February 28, 2019 at 1pm - NO5, Solvay Room

Towards Physically-Secure Implementations (& the Need of Theory, Practice and Open Designs)

François-Xavier Standaert

Université Catholique de Louvain

Université Catholique de Louvain

In this talk, I will survey recent approaches/results to obtain physical security against side-channel attacks exploiting leakages, such as an implementation's power consumption. After a brief introduction and motivation, I'll describe how these attacks proceed (i.e., the so-called standard DPA setting) and why purely hardware-level (practical, heuristic) countermeasures alone cannot solve the problem. I will then discuss how the impact of hardware-level countermeasures can be amplified thanks an algorithmic-level countermeasure called masking, how this amplification can be formally analyzed, and the implementation challenges that physical defaults can imply for the secure implementation of masking. I will conclude by discussing the need of an open approach to physical security, and the interest of re-designing cryptographic algorithms and protocols for this purpose.

Francois-Xavier Standaert received the Electrical Engineering degree and PhD degree from the Universite catholique de Louvain, respectively in 2001 and 2004. In 2004-2005, he was a Fulbright visiting researcher at Columbia University, Department of Computer Science, Crypto Lab and at the MIT Medialab, Center for Bits and Atoms. In 2006, he was a founding member of IntoPix s.a. From 2005 to 2008, he was a post-doctoral researcher of the Belgian Fund for Scientific Research (FNRS-F.R.S.) at the UCL Crypto Group. Since 2008 (resp. 2017), he is associate researcher (resp. senior associate researcher) of the Belgian Fund for Scientific Research (FNRS-F.R.S). Since 2013 (resp. 2018), he is associate professor (resp. professor) at the UCL Institute of Information and Communication Technologies, Electronics and Applied Mathematics (ICTEAM). In 2011, he was awarded a Starting Independent Research Grant by the European Research Council. In 2016, he has been awarded a Consolidator Grant by the European Research Council. From 2017 to 2020, he will be board member (director) of the International Association for Cryptologic Research (IACR). His research interests include cryptographic hardware and embedded systems, low power implementations for constrained environments (RFIDs, sensor networks, ...), the design and cryptanalysis of symmetric cryptographic primitives, physical security issues in general and side-channel analysis in particular.

The speaker is hosted by the Quality and Security of Information Systems Group.

Wednesday January 23, 2019, 11:00 AM, room: NO5, Solvay Room

Data-driven approach to the Air Traffic Flow Management problem

Optimization models for Air Traffic Flow Management (ATFM) select, for each flight, suitable trajectories with the aim of reducing congestion of both airports and en-route sectors, and maximizing the Air Traffic Management system efficiency. Recent models try to include as accurate as possible information on airspace capacity as well as on Airspace Users route preferences and priorities, as suggested by recent SESAR (Single European Sky ATM Research) programs. In this direction, we analyze flight trajectories queried from Eurocontrol DDR2 data source. We learn homogeneous trajectories via clustering, and we apply data analytics (mainly based on tree classifiers, support vector machines and multiple regression) to explore the relation between grouped trajectories and potential choice-determinants such as length, time, en-route charges, fuel consumption, aircraft type, airspace congestion etc. The associations are evaluated and the predictive value of determinants is validated and analyzed. For any given origin-destination pair, this ultimately leads to determining a set of flight trajectories and information on related Airspace Users' preferences that feed optimization models for ATFM.

Luigi De Giovanni is Associate Professor of Operations Research at University of Padua (Italy), Department of Mathematics "Tullio Levi-Civita". He received the Master Degree cum laude in Computer Engineering from "Politecnico" University of Turin (Italy) in 1999, and the PhD degree in Computer and System Engineering from the same university in 2004. He has been visiting PhD student at Université Libre de Bruxelles (ULB) in 2003. He has been post-doc researcher at the Computer Science Department of ULB from 2004 to 2006, and at the Computer and Management Engineering Department of Marche "Politecnica" University in Ancona (Italy) from 2006 to 2007. He has been Assistant Professor of Operations Research at University of Padua from October 2007 to September 2018. His main research interests cover mathematical programming and meta-heuristic methods and models for combinatorial optimization and their application to telecommunication network configuration, transportation, logistics, scheduling, air traffic and airport optimization.

The speaker is hosted by GOM.

Monday May 28, 2018, 12:00 PM, room: NO5, Solvay Room

Social norm complexity and human cooperatio

Francisco C. Santos
(Department
of Computer Science and Engineering of Instituto Superior Técnico
(IST), University of Lisbon, Portugal)

Explaining the emergence of cooperation is one of the biggest challenges science faces today. Indeed, cooperation dilemmas occur at all scales and levels of complexity, from cells to global governance. Theoretical and experimental works have shown that status and reputations can provide solutions to the cooperation conundrum. These features are often framed in the context of indirect reciprocity, which constitutes one of the most elaborate mechanisms of cooperation discovered so far. By helping someone, individuals may increase their reputation, which can change the predisposition of others to help them in the future. The reputation of an individual depends, in turn, on the social norms that establish what characterises a good or bad action. Such norms are often so complex that an individual’s ability to follow subjective rules becomes important. In this seminar, I will discuss a simple evolutionary game capable of identifying the key pattern of the norms that promote cooperation, and those that do so at a minimum complexity. This combination of high cooperation and low complexity suggests that simple moral principles, and informal institutions based on reputations, can elicit cooperation even in complex environments.

Francisco C. Santos is an Associate Professor of the Department of Computer Science and Engineering of IST, University of Lisbon (Portugal). He is interested in applying scientific computing and modelling tools to understand collective dynamics in social and life sciences. He has been working on problems related to the evolution of cooperation, the origins of social norms, network science, and environmental governance, among others. He obtained a PhD in computer science from the Université Libre de Bruxelles in 2007.

The speaker is hosted by MLG.

Tuesday March 27, 2018, 12:15 PM, room: Forum F

Hub Location Problems: Applications, Models and Solution Methods

Hubbing is commonly used in airlines, cargo delivery and telecommunications networks where traffic from many origins to many destinations are consolidated at hubs and are routed together to benefit from economies of scale. Each application area has its own specific features and the associated hub location problems are of complex nature. In the first part of this talk, I will introduce the basic hub location problems, summarize important models and results and mention the shortcomings of these in addressing real life situations. In the second part, I will introduce new variants of the hub location problem that incorporate features such as hierarchical and multimodal networks, service of quality constraints, generalized allocation strategies and demand uncertainty. I will conclude the talk with an ongoing work on a joint problem of hub location, network design and dimensioning.

Hande Yaman received her B.S. and M.S. degrees in Industrial Engineering from Bilkent University, and her Ph.D. degree in Operations Research from Universite Libre de Bruxelles. She joined the Department of Industrial Engineering at Bilkent University in 2003. She spent a year as a visiting researcher at CORE, Universite catholique de Louvain. Her research interests are in exact methods for mixed integer programming with applications in production planning, logistics, and network design.

The speaker is hosted by GOM.

Thursday April 26, 2018, 13:30PM, room: NO5, Solvay Room

Column-parity mixing layers in cryptography

Joan Daemen
(Institute for Computing and
Information Sciences at the Radboud University and STMicroelectronics)

Mixing layers, such as MixColumns in the AES, are an essential ingredient that can be found in the round function of most modern block ciphers and permutations. We study a generalization of the mixing layer in Keccak-f, the permutation underlying the NIST standard SHA-3 and the authenticated encryption schemes Keyak and Ketje. We call this generalization column-parity mixing layers and investigate their algebraic and diffusion properties and implementation cost. We demonstrate their competitiveness by presenting a fully specified 256-bit permutation with strong bounds for differential and linear trails.

Joan Daemen, who obtained his PhD in cryptography at the COSIC research group of the KULeuven, is a Belgian cryptographer who co-designed the Rijndael encryption scheme which was selected by the NIST as the Advanced Encryption Standard (AES), as well as the Keccak cryptographic hashing algorithm which was selected also by the NIST as the new SHA-3 standard hash function. He is also the author of many other symmetric cryptographic primitives. In 2017 Joan Daemen won the Levchin Prize for Real World Cryptography. Joan Daemen divides his time between the Institute for Computing and Information Sciences at the Radboud University and STMicroelectronics in Belgium.

The speaker is hosted by QualSEC.

Thursday October 12, 2017, 12:15 PM, room: Forum G

The Cache Oblivious Model of Computation

John Iacono
(New York University / ULB)

In the standard model of computation often taught in computer science courses one identifies elementary operations and counts them in order to obtain the runtime. However, given the complexity of computing hardware, this measure often does not correlate well with actual observed runtime on a computer; accessing n items sequentially or randomly typically have runtimes that differ by several orders of magnitude. In this talk I will present the cache-oblivious model of computation, a model that was introduced by Prokop in 1999 and is relatively easy to reason with, by modeling the multilevel caches that are a defining feature of the cost of modern computation. After presenting the model, several data structure and algorithms that illustrate design techniques to develop cache-obliviously optimal structures will be presented.

The speaker is hosted by the Algorithms Group.