Seminars

Title: Regularizing the delay of enumeration algorithms
Zoom link: univ-lille-fr.zoom.us/j/95419000064
Abstract: 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 some solutions or to transform the
solutions as they are outputted with a stream-like algorithm, a relevant measure
of the complexity of an enumeration algorithm is the delay 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 result in the output of at least t solutions. Of
course, by storing each solution seen and outputting them regularly, one can
simulate a polynomial delay but if the number of solutions is large, it 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
algorithm into polynomial delay algorithm using polynomial space.

This is joint work with Yann Strozecki.