ULB
Computer Science Seminars
Université Libre de Bruxelles
Computer Science Department


Practical information

Map: Campus de la Plaine. For more information, please contact John Iacono (john dot iacono at ulb dot be).
November 9th 2022 at 12:15 - Solvay Room
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
Irina Kostitsyna
TU Eindhoven

Abstract

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.

Bio

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.

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as algorithms for the purpose of this requirement.
December 2nd 2022 at 12:15 - Forum F
Deliveries with cargo-bike and robot
Diego Cattaruzza
Centrale Lille

Abstract

 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

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as optimization for the purpose of this requirement.

Past Seminars

October 27th 2022 at 11:00 - Solvay Room (NO building, 5th floor)
Collective Learning Dynamics
Wolfram Barfuss
University of Tübingen

Abstract

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.

Bio

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.

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as machine learning for the purpose of this requirement.
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

Abstract

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.

Bio

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.

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as security for the purpose of this requirement.
April 27th 2022 at 12:15 - Room P.Forum.F
Proximity-based authentication: Secure realisation of distance bounding protocols
Dave Singelée
KULeuven

Abstract

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.

Bio

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.

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as security for the purpose of this requirement.
March 31th 2022 at Noon - Location S.R42.4.502
Note Location on Solbosch!!
Learning multidirectional functional models with MERCS
Hendrik Blockeel
KU Leuven

Abstract

Ensembles of decision trees are among the most frequently used predictive models, with Random Forests and Gradient Boosted Trees as their most successful representatives. In this talk, I will discuss another instantiation: multi-directional ensembles of decision trees, as implemented in the MERCS approach. In a multi-directional ensemble, different trees may have different targets, so that the ensemble as a whole can be used to predict any variable from any other variable. This makes MERCS models very flexible in terms of the tasks they can perform. At the same time, they inherit the efficiency, accuracy, versatility and ease-of-use of decision tree ensembles. I will discuss the advantages and challenges of learning MERCS models and illustrate how they can be used for a variety of tasks.

Bio

Hendrik Blockeel (PhD in Computer Science, 1998, KU Leuven) is a full professor ("gewoon hoogleraar") at KU Leuven. From 2007 till 2016 he was also affiliated with Leiden University. His research interests include theory and algorithms for machine learning and data mining in general, with a particular focus on relational learning, graph mining, probabilistic logics, inductive knowledge bases, and applications of these techniques in the broader field of computer science, bio-informatics, and medical informatics.

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as artificial intelligence for the purpose of this requirement.
March 24th 2022 at Noon - Solvay Room (5th Floor NO building)
The algorithmic challenges of local fast re-routing
Stefan Schmid
Technical University of Berlin

Abstract

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.

Bio

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.

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as optimization for the purpose of this requirement.
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

Abstract

Cryptographic protocols offer complex security functionality by combining cryptographic primitives, communication, and interaction with users and functional components. This presentation will offer a perspective on the lifecycle of cryptographic protocols: from design, analysis, specification to standardization, implementation, deployment and maintenance. Making the step from an academic design to a real-world protocol is far from trivial and can severely complicate matters. Based on several examples we will dive into the issues encountered and potential solutions.

Bio

 Jens Hermans is currently the CEO of nextAuth, a spin-off company of KU Leuven on secure and user friendly mobile authentication that he co-founded in 2019. Before that, he was a researcher at the COSIC group, KU Leuven (PhD in 2012). His main research interest is security and cryptography for the real world: the analysis and design of protocols, human-computer interaction in security and, in general, overall security architectures and solutions for challenging applications such as authentication and voting.

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as security for the purpose of this requirement.
March 2nd 2022 at Noon - Forum A
Rectilinear convex hull of points in 3D
Carlos Seara
Universitat Politècnica de Catalunya (UPC BarcelonaTech)

Abstract

 Let P be a set of n points in R^3 in general position, and let RCH(P) be the rectilinear convex hull of P. In this talk we show how we obtain an optimal O(n log n)-time and O(n)-space algorithm to compute RCH(P). We also obtain an efficient O(n\log^2 n)-time and O(n log n)-space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of P as we rotate R^3 around the z-axis. Finally, we study some properties of the rectilinear convex hulls of point sets in R^3.

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as algorithms for the purpose of this requirement.
February 8th 2022 at Noon - OF2072-2074
Advances on the Balanced Minimum Evolution Problem
Daniele Catanzaro
Center for Operations Research and Econometrics (CORE)

Abstract

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.

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as optimization for the purpose of this requirement.
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

Abstract

 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.

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as artificial intelligence for the purpose of this requirement.
Friday November 5th 2021 at 12:15 PM - Solvay Room (5th Floor NO building)
Optimization problems in graphs with locational uncertainty
Michaël Poss
LIRMM

Abstract

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.

Bio

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.

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as optimization for the purpose of this requirement.
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

Abstract

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.

Bio

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

Note for INFO-F530 Students

Each student will follow one seminar from the following topics : algorithms, security, optimization and artificial intelligence. This seminar is classified as algorithms for the purpose of this requirement.
February 10th, 2020, 12:30 PM - Solvay Room (NO5)
Fare Evasion in Transit Networks
Jannik Matuschke
Research Center for Operations Management, KU Leuven

Abstract

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.

Bio

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)

Slides (PDF)

Abstract

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.

Bio

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:

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)

Abstract

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.

Bio

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
João Gama (INESC TEC, University of Porto)

Slides (PDF)

Abstract

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.

Bio

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

Abstract

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.

Bio

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
Luigi De Giovanni (Dipartimento di Matematica "Tullio Levi-Civita", Università di Padova (Italy)

Slides (PDF)


Abstract

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.

Bio

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)

Abstract

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.

Bio

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
Hande Yaman (Bilkent University)

Abstract

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.

Bio

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)

Abstract

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.

Bio

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)

Abstract

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.