Signed tree models

Speaker(s)

Édouard Bonnet

Affiliation

CNRS, ENS de Lyon

Language of the talk

English

Date

March 27, 2026, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

A signed tree model was recently introduced as a mean to encode a graph in a tree structure with two types of additional edges, positive and negative ones.
Most important factorial classes (i.e., with growth 2^O(n log n)) admit (almost) sparse signed tree models, that is, where the number of additional edges is (almost) linear.
We survey what is currently known on building signed tree models, using them to design faster algorithms (notably for distance-based problems and matrix multiplication), and ask several open questions on this recent topic. 

The talk will be mainly based on https://arxiv.org/abs/2405.09011 and https://arxiv.org/abs/2602.16605.

---