12 June 2026 at 11:00 Amphitheater (Battelle D)

In this talk, I will present my Bachelor work on maximizing source and destination sets in directed graphs. The approach exploits structural properties of these graphs together with classical graph-theoretic results, leading to an efficient polynomial-time algorithm.

22 May 2026 at 11:00 Amphitheater (Battelle D)

In this talk, I will give an overview of quantum computing. I will start by describing a bit the history of quantum mechanics, introducing the notation and quickly explaining the formalism behind, how everything started and the first experiments/theoretical observations by pioneers in the field. I will introduce (and briefly explain) some of the most influential algorithm developed just after the impact of Feynman's proposal, among which the notably Shor's algorithm and Grover's algorithm. We will take a detour in complexity theory, and see how quantum complexity fits in this landscape, by mentioning known landmark results and what is (arguably) the most intriguing open question in this landscape. We will then move to what is arguably the most "practical" use case of near-term quantum computers, and their capability of sampling and searching. Finally, I will briefly survey the latest results, the progress made on the sampling and searching paradigm, the quest for quantum advantage and the impact of quantum computation in cryptography.

27 March 2026 at 11:00 Amphitheater (Battelle D)

We propose a new general-purpose comparison-free sorting algorithm called CastSort. This algorithm is close to Proxmap sort, a kind of bucket sort. Our main addition is a function that limits the number of recursions. Analyzing the theoretical time complexity of this algorithm is challenging; however, it should be really close to O(n). Based on experimental results, CastSort seems to outperform the best implementations of QuickSort (namely, qsort of the glibc). It has also been tested against ProxmapSort on exponentially distributed values and shows improvements in both the max recursion depth and running time. 

20 March 2026 at 11:00 Amphitheater (Battelle D)

In December 2025, a group of six students from the University of Geneva went to participate in the SWERC programming contest (https://swerc.eu/2024/). The competition consists of solving algorithmic problems and coding the solutions efficiently. One of the students, Théo, will present some of the problems he found interesting, and we will try to solve them together. This slightly special session promises to be quite entertaining!rtissante !

13 March 2026 at 11:00 in Amphitheater (Battelle D)

We present topological methods for distributed computing, as introduced by Herlihy & Shavit in the 2000s. We start with the basics of simplicial complexes as a way to encode distributed information. Then we summarize the computability results for asynchronous wait-free shared memory that awarded them the Gödel prize. We consider also colorless tasks for which there are simple geometric characterizations, and present more recent results and applications of these techniques. We end this survey by a discussion about recent lines of work that extend these methods to more general models, including dynamic networks.

27 February 2026 at 11:00 (Amphitheater Battelle D)

In a recreative column of the Scientific American, Martin Gardner presented in 1973 a game consisting of computing an optimal trajectory for a vehicle on a race track, subject to acceleration constraints in discrete space~$\mathbb{Z}^2$. In this acceleration model, each step consists of changing the position of the vehicle by a vector in $\mathbb{Z}^2$, with the constraints that two consecutive vectors differ by at most one unit in each dimension. We investigate three problems related to this model in arbitrary dimension in open space (no obstacles), where a \emph{configuration} of the vehicle consists of its current position and the last-used vector (concretely, a value in $\mathbb{Z}^d \times \mathbb{Z}^d$). The three problems are the following. In \textsc{Branching Cost}, two configurations are given and the goal is to compute the minimum number of intermediate configurations (length of a trajectory) between the two configurations. \textsc{Branching Trajectory} has the same input and asks for a description of the corresponding trajectory. Finally, \textsc{Multipoint Trajectory} asks for an optimal trajectory that visits given points $p_1,\dots,p_n$ \emph{in a prescribed order}, starting and ending with zero-speed configurations. We obtain a variety of results. First, we revisit known approaches solving \textsc{Branching Cost} in 2D, clarifying the analysis and showing that this problem can be solved in constant time in any fixed number of dimensions $d$ (more generally, in $O(d \log d)$ time). Then, we show that \textsc{Branching Trajectory} can also be solved in constant time for any fixed $d$, despite the fact that the length of the trajectory is not constant. A key ingredient here is to show that there always exists \emph{one} optimal trajectory that can be compactly represented by $O(1)$ intermediate configurations. Finally, we turn our attention to \textsc{Multipoint Trajectory}. Paradoxically, the absence of obstacles poses new challenges here, in comparison to previous settings where having walls on the race track dramatically reduces the search space for a trajectory. More precisely, we collect theoretical and experimental evidence that the speed cannot be trivially bounded; that local decisions may be impacted by points that are arbitrarily far in the visit order; and that an optimal trajectory may require significant excursions out of the convex hull of the points. In this context, we still establish conservative speed bounds that a natural dynamic programming (DP) algorithm can exploit to solve reasonably large instances efficiently. This is joint work with Arnaud Casteigts and Pierre Leone.

10 February 2026 at 11:00 in Battelle A (Room 319)

Given a network with dynamic pairwise connections, we may be interested in knowing whether the entire network could be (indirectly) infected by a small number of initially compromised nodes. Also, if which pairs must be connected is prescribed, but the order in which the connections should occur is not, we may wish to schedule these in such a way that the number of initially compromised nodes which is needed to reach the entire network is maximized. These problems are naturally modelled using temporal graph theory, which extends classical graph theory to incorporate the dynamism inherent to many real-world systems.
In this talk, we will (gently) introduce temporal graphs and temporal reachability, then define and study the aforementioned problems using this formalism – as the Temporal Reachability Dominating Set (TaRDiS) and MaxMinTaRDiS problems, respectively. We will then present some algorithms and hardness proofs for the corresponding decision problem. The first half of the talk will focus on nonstrict temporal reachability (which is a good model for interconnection networks) and the second half of the talk will discuss strict temporal reachability (a good model for biological contagion) and happy temporal graphs (which are in some sense abstractions of asynchronous systems, sitting at the intersection of strict and nonstrict models).
This talk is based on the paper Temporal Reachability Dominating Sets: contagion in temporal graphs

23 January 2026 at 14:00 in Battelle A (Room 425)

Power grids are (and will remain) a crucial part of modern societies' infrastructures. At the same time, our capabilities of monitoring on power grid are increasing. In such a context, it is surprising that nowadays, some part of the grid remain unknown to system operators. In this talk we will review some inference techniques that have been developped both for high- and low-voltage grids. We will then see that despite the large toolbox of inference methods available, grid inference is not yet a settled game.

16 January 2025 at 11:00 in Battelle A (Room 425)

In this talk, I will present my Bachelor project on efficiently enumerating temporal graphs when the edges can appear several times (nonsimple temporal graphs). The procedure exploits special properties of these graphs related to automorphisms and matchings, which give rise to group theoretic questions of independent interest.

16 December 2025 at 14:00 in Room 425 (Battelle A)

A partition of a positive integer n is a non-increasing sequence of positive integers whose sum is n. A partition identity is a theorem stating that for all n, the number of partitions of n satisfying some conditions equals the number of partitions of n satisfying some other conditions. The Rogers-Ramanujan identities state that for all n, there are as many partitions of n where parts differ by at leat two as partitions of n into parts congruent to 1 or 4 modulo 5. In addition to this combinatorial version, there is also an equivalent analytic formulation (where an infinite sum equals an infinite product) and the correspondence between the two versions can be made using generating functions. The Andrews-Gordon identities, who generalise the Rogers-Ramanujan identities, are among the most important partition identities, and also exist both as combinatorial and analytic versions. However, while the product side of the analytic version clearly corresponds to partitions with congruence conditions, it is not obvious at first sight that the sum side version is the generating function for the partitions with difference conditions that appear in the combinatorial version. It was originally proved by George Andrews using recurrences, and then bijectively by Ole Warnaar using particle motion. In this talk, we will first explain the basics of partition identities and their connection to generating functions. We will then explain and generalise the particle motion bijection, and show that our generalisation can be used to prove many new and known identities of the Andrews-Gordon type, including broad generalisations of the Andrews-Gordon identities. This is based on joint work with Jihyeug Jang, Frédéric Jouhet and Isaac Konan.

21 November 2025 at 11:00 in Room 404 (Battelle A)

Typst is a new typesetting system designed as a fast and modern alternative to LaTeX. Designed forscientific and technical writings, Typst aims at maximizing the pleasure to use it without sacrificing its capabilities. Despite its relatively young age, Typst hosts a very dynamic community with a wide library of modules and templates. During this talk, we will present you the basics of Typst, as well as several concepts useful for scientific writing such as math, bibliography, etc. We will also introduce the unusual scripting language that give Typst its solid foundations. (Note that this talk will likely be given in French.)

10 November 2025 at 14:00 in Room 301 (Battelle A)

We propose an extension of the decoder Transformer that conditions its generative process on random latent variables which are learned without supervision thanks to a variational procedure. Experimental evaluations show that allowing such a conditioning translates into substantial improvements on downstream tasks.

28 October 2025 at 14:00 in Room 404 (Battelle A)

Assume given tasks that need to be repeated every week at specific times and a number of indistinguishable workers to perform them. We address the problem of assigning these periodic tasks in a balanced way, i.e., so that each worker performs each task with the same frequency over the long term. Two versions of this problem are considered: the basic version, for which the sole constraint is that a worker cannot perform two tasks at the same time, and the extended version where additional constraints on the feasibility of weekly schedules can be introduced. This work shows that, for the two versions of the studied problem, whenever there exists a balanced assignment, such an assignment can always be made periodic. Furthermore, for the basic version, we establish a necessary and sufficient condition for the existence of a balanced assignment , which can be verified in polytime. For the extended version, a sufficient condition of existence is established as well. As a tool to obtain our results, we introduce a problem of pebbles moving along arcs on an arc-colored directed graph and that need to visit each arc with the same frequency in the long term. This problem and the results obtained about it might be of independent interest. Joint work with Héloïse Gachet

3 October 2025 at 11:00 in Room 404 (Battelle A)

In this talk, we will focus on the reconfiguration of nowhere-zero flows in graphs, a problem at the intersection of graph theory and algorithmic reconfiguration. Our aim is to understand how one nowhere-zero flow can be transformed into another through a series of elementary steps, while maintaining the nowhere-zero flow condition along the way. We will explore the duality problem for planar graphs, the so-called group flows, and how the connectivity of the reconfiguration graph depends on the group structure and cardinality. Among other results, we prove that the reconfiguration graph of planar graphs with nowhere-zero 7-flows is connected.

19 September 2025 at 11:30 in Room 404 (Battelle A)

Cloud service providers can act maliciously and tamper with the data. Proofs of storage enable clients to verify data integrity. In the first part of the talk, I will present the concept of proofs of storage and present some constructions. I will then discuss the concept of proofs of storage and its relation to data availability and scalability of blockchains. In the last part we I introduce the concept of proofs of storage to prove facts about historical blockchain data.
Bio: Sushmita Ruj is Faculty of Engineering Lead of UNSW Institute for Cybersecurity, IFCYBER and Associate Professor in the School of Computer Science and Engineering at UNSW, Sydney. Her research interests are in applied cryptography, post quantum cryptography, blockchains and privacy enhancing technologies. She designs practical , efficient, and provably secure protocols that can be deployed in real-world applications. She led a Cybersecurity CRC project on Privacy Preserving Data Sharing that won an NSW iAward (Innovation Award). She has won several competitive grants like Australian Research Council grant, Samsung GRO Award, NetApp Faculty Fellowship, Cisco Academic Grant. She is an Associate Editor of IEEE Transactions on Information Forensics and Security. Sushmita is a senior member of both ACM and IEEE. More details can be found on her homepage

8 July 2025 at 11:00 in Room 319 (Battelle A)

Community detection is a popular approach to understand the organization of interactions in static networks. For that purpose, the Clique Percolation Method (CPM), which involves the percolation of k-cliques, is a well-studied technique that offers several advantages. Besides, studying interactions that occur over time is useful in various contexts, which can be modeled by the link stream formalism. The Dynamic Clique Percolation Method (DCPM) has been proposed for extending CPM to temporal networks. However, existing implementations are unable to handle massive datasets. We present a novel algorithm that adapts CPM to link streams, which has the advantage that it allows us to speed up the computation time with respect to the existing DCPM method. We evaluate it experimentally on real datasets and show that it scales to massive link streams. For example, it allows to obtain a complete set of communities in under twenty-five minutes for a dataset with thirty million links, what the state of the art fails to achieve even after a week of computation. We further show that our method provides communities similar to DCPM, but slightly more aggregated. We exhibit the relevance of the obtained communities in real world cases, and show that they provide information on the importance of vertices in the link streams..

24 June 2025 at 11:00 in Room 319 (Battelle A)

Since their introduction by Gale and Shapley, stable matchings have been studied extensively by the economics, computer science, and optimization communities. One reason for such popularity is their rich mathematical structure. In particular, under quite general assumptions on the preferences of agents, stable matchings can be naturally ordered to form a lattice (in the partial order sense). This structure has been exploited to prove polynomial-time algorithms, NP-hardness results, and gain structural insights into the problem. In this talk, I will survey results on the relationship between stable matchings and lattices, starting from the distributive lattice structure on Gale and Shapley's original 1-to-1 marriage model, until recent joint work with Christopher En (Columbia) on the non-distributive lattice structure of more general many-to-many models, and their relationship with antimatroids.

27 May 2025 at 11:00 in Room 319 (Battelle A)

We know since 2016 that temporal graphs in general do not admit sparse spanners: Some dense temporal graphs (with quadratically many edges) cannot be sparsified while preserving all-pair communication (temporal connectivity). This result is a bad news for efficient communication in dynamic networks (at least, theoretically ). In this talk, I will show that the special case of temporal cliques (the underlying graph is a complete graph) is nicer: in these graphs, spanners of size O(n log n) always exist, and so, whatever the schedule of the edges. The original bound was obtained in 2019 [1]. The proof was subsequently simplified by Angrick et al. [2]. In this talk, I will present yet another version of the proof from [3] that relies on a single unified principle called dismountability. We will go through the complete proof step by step, all the arguments being elementary (no special background is required).
[1] A. Casteigts, J. Peters, J. Schoeters: Temporal Cliques admit Sparse Spanners (ICALP 2019)
[2] S. Angrick, B. Bals, T. Friedrich, H. Gawendowicz, N. Hastrich, N. Klodt, P. Lenzner, J. Schmidt, G. Skretas, A. Wells: How to Reduce Temporal Cliques to Find Sparse Spanners (ESA 2024)
[3] D. Carnevale A. Casteigts, T. Corsini: Dismountability in Temporal Cliques Revisited (SAND, 2025)

15 April 2025 at 11:00 in Room 404 (Battelle A)

Algebraic data types are a way of formally describing the structure of compound types, which form the basis of data structures such as lists, trees, etc. We will look at some unexpected and useful properties that arise from this formalism, particularly for the description and analysis of recursive data structures.

11 March 2025 at 11:00 in Room 319 (Battelle A)

The presentation will discuss a research program aiming at automating model generation and detection of design flaws in early development stages by automatically generating and exploiting directed colored graphs representing the architecture and behavior of systems. The proposed framework should serve as a computational companion to developers, designers, and decision makers, providing a new form of computational support. The early development phases are characterized by ill-defined design problems using a mixture of text, functional descriptions, requirements combining numerical and textual data. In these design phases, the generation of models, the reasoning and the detection of weaknesses or limitations still rely heavily on human expertise, despite the enormous increase in complexity that overwhelms human cognitive capabilities. In the 1990s, a branch of machine learning developed methods for qualitative reasoning. A mathematical machinery that exploits the decomposition of units into elementary dimensions, originally developed at the IBM Research Centre, combined power laws, contact variables and partial derivatives to model the interactions of systems’ variables using qualitative reasoning . The approach has since been extended to include problem formulation in the form of directed graphs, and the ability to detect and resolve inconsistencies using inventive principles from TRIZ. The long-term aim is to develop an approach towards fully automatic generation of models that can be simulated, used to control complex systems, evaluate, and test design hypotheses, and be used to improve design solutions. The application domains envisioned for this approach are explainable and parsimonious machine learning model generation, and design of cyber-physical systems.

20 February 2025 at 15:00 in Room 319 (Battelle A)

Roland Bouffanais (University of Geneva)

Collective Computing by Complex Intelligent Robotic Systems