Computer Science Seminars

Université Libre de Bruxelles

Computer Science Department

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.