Calendrier des animations scientifiques

Cographs are among the best-studied graph classes. Among
other characterizations, they are precisely those graphs G that can be
represented by a unique rooted tree (T,t), called cotree, whose leaf
set is V(G) and whose non-leaf vertices v are assigned a label t(v) in
{0,1}. Every cograph G is explained by its cotree, that is, {x,y} is
an edge of G if and only if the lowest common ancestor of x and y in T
has label 1.

Recent advances in mathematical biology have shown that cographs are
intimately linked to pairwise relationships between genes. For
example, the orthology relation collects all pairs of genes whose last
common ancestor in their evolutionary history was a speciation event
(or, equivalently, has label 1) and thus forms a cograph. In many
applications, however, graphs G usually violate the property of being
a cograph and thus cannot be represented by a tree.

In this talk, I will introduce the novel concept of Explicit Modular
Decomposition, that aims at representing non-cographs with suitable
{0,1}-labelled rooted structures. I will then focus on graphs that can
be explained by rooted networks (N,t) whose bi-connected components
are edge-disjoint. These graphs, called GaTEx, can be recognized in
linear-time and are characterized by a set of 25 forbidden induced
subgraphs. I will present some of their theoretical properties, and I
will conclude with a generalization of the concepts of Explicit
Modular Decomposition and GaTEx graphs to more general discrete
structures.

This is joint work with Marc Hellmuth and Anna Lindeberg.

We initiate the study of tree structures in the context of
scenario-based robust optimization. Specifically, we study Binary Search
Trees (BSTs) and Huffman coding, two fundamental techniques for
efficiently managing and encoding data based on a known set of
frequencies of keys. Given a number of distinct scenarios, each defined
by a frequency distribution over the keys, our objective is to compute a
single tree of best-possible performance, relative to any scenario.

We consider, as performance metrics, the competitive ratio, which
compares multiplicatively the cost of the solution to the tree of least
cost among all scenarios, as well as the regret, which induces a
similar, but additive comparison. For BSTs, we show that the problem is
NP-hard across both metrics. We also obtain an optimal competitive
ratio that is logarithmic in the number of scenarios. For Huffman Trees,
we likewise prove NP-hardness, and we present an algorithm with
logarithmic regret, which we prove to be near-optimal by showing a
corresponding lower bound. Last, we give a polynomial-time algorithm for
computing Pareto-optimal BSTs with respect to their regret, assuming
scenarios defined by uniform distributions over the keys. This setting
captures, in particular, the first study of fairness in the context of
data structures. We provide an experimental evaluation of all
algorithms. To this end, we also provide mixed integer linear program
formulation for computing optimal trees.

Joint work with Spyros Angelopoulos, Christoph Dürr and Alex Elenter.

Threshold Signatures allow n parties to share the power of issuing digital signatures so that any coalition of size at least t + 1 can sign, whereas groups of t or less parties cannot. Over the last few years, many schemes have addressed the question of realizing efficient threshold variants of EC-DSA signatures. Moreover, the NIST has announced its intention to standardize threshold EC-DSA schemes (https://csrc.nist.gov/projects/threshold-cryptography). This paper is a long version of the threshold EC-DSA scheme from Castagnos et al. (PKC 2020), which presented a solution aiming to reduce bandwidth consumption. The main contribution of the original article was a new variant of the Gennaro and Goldfeder protocol, from ACM CCS 2018, which avoids the range proofs that they required, while retaining provable security against malicious adversaries in the dishonest majority setting. The key ingredient to this achievement was the adoption of the CL linear homomorphic encryption scheme, based on class groups, which significantly reduces bandwidth consumption compared to existing schemes and achieves faster signature generation for high levels of security.

In this presentation, we will recall the construction of our original work (Castagnos et al. (PKC 2020)). Then, we will present new techniques to extend it. This is based upon our new revised version, which is currently an ongoing work, where we simplify setup and key generation by relying on different zero knowledge techniques for class groups. Moreover, we provide an optimized open source implementation of our new threshold EC-DSA protocol using the BICYCL library (JoC 2023). This version achieves even better bandwidth, giving one of the most compact threshold EC-DSA schemes. Key generation and signing times are on par with other schemes and can be more efficient, depending on the values of t, n and the security parameter. For instance, for n = 11, t = 10 and 128 bits of security, signing takes about a second while each party exchanges 31kB.

Graph modification problems are computational tasks where the goal is to change an input graph G using operations from a fixed set, in order to make the resulting graph satisfy a target property, which usually entails membership to a desired graph class. Some well-known examples of operations include vertex deletion, edge deletion, edge addition and edge contraction. In this talk we address an operation known as subgraph complementation.

Given a graph G and a subset S of its vertices, the subgraph complement G ⊕ S is the graph resulting from complementing the edge set of the subgraph induced by S in G.
We say that a graph H is a subgraph complement of G if there is an S such that H is isomorphic to G ⊕ S.

For a graph class C, the Subgraph Complementation to C problem is the problem of deciding, for a given graph G, whether G has a subgraph complement in C. The complexity of this problem has been settled for many classes C, including classes forbidding a single induced subgraph, classes of bounded degeneracy and regular graphs.

In this talk, we focus on classes of graphs of minimum/maximum degree upper/lower bounded by some value k, including the case of regular graphs. We show that the cases left open by Antony et al. (Information Processing Letters, 2025) are NP-complete and also show that they are in FPT, parameterized by k.

Based on joint work with Ivo Koch and Nina Pardal.