Skip to main navigation Skip to Content

SPEAKER: Yann Strozecki, Université Paris Diderot

Dept. of Computer Science, University of Toronto

TITLE: Enumeration complexity: the monomials of a polynomial

ABSTRACT:

Enumeration is the task of generating all solutions of a problem. The complexity of an enumeration is measured by both the total time to enumerate all solutions and the delay between each solution.We revisit the famous problem of polynomial interpolation with an enumeration point of view and give several good algorithms with regard to the delay. We also explain how these results can be used to solve more classical enumeration problems on graphs.