### 6 décembre 2021

**Florent Capelli**(INRIA Lille équipe LINKS)

Enumeration algorithms are algorithms whose goal is to

output the set of all solutions to a given problem. There exists

different measures for the quality of such algorithm, whose relevance

depends on what the user wants to do with the solutions set.

If the goal of the user is to explore a subset of solutions or to

transform the solutions as they are outputted with a stream-like

algorithm, a relevant measure of the complexity in this case is the

delay, that is, the maximal time between the output of two distinct

solutions. Following this line of thoughts, significant efforts have

been made by the community to design polynomial delay algorithms, that

is, algorithms whose delay between the output of two new solutions is

polynomial in the size of the input.

While this measure is interesting, it is not always completely

necessary to have a bound on the delay and it is enough to ask for a

guarantee that running the algorithm for O(t poly(n)) will produce at

least t solutions. While algorithms having this property can be

transformed into polynomial delay algorithm, the naive transformation

may result in a blow up in the space used by the enumerator.

In this talk, we will present a new technique that allow to transform

such algorithms into polynomial delay algorithm with only a polynomial

overhead on the space.