Signed tree models

Prelegent(ci)

Édouard Bonnet

Afiliacja

CNRS, ENS de Lyon

Język referatu

angielski

Termin

27 marca 2026 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

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.

---