LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Past Seminars
Methods for Enumeration
- Date
- Wednesday, April 11 2012 at 02:00PM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Yann Strozecki (LRI, Paris-Sud 11)
I will present enumerations problems, that is we want to produce the set of solutions of a problem. Several methods to design low complexity enumeration algorithms will be presented. In these settings we want both the total time and the delay between two solutions to be small.
First we will use representation of combinatorial problems by polynomial to reduce enumeration to multivariate interpolation. This leads to probabilistic algorithms for problems on graphs, hypergraphs, probabilistic automata ...
Queries over databases or trees are natural examples of enumeration problems. I will present first-order queries with free second-order variables and explain how to solve them when their quantifier depth is small.
We are also interested in a verification problem: finding witnesses that two systems (automata, MDP ...) are different. Since the number of witnesses may be infinite, their enumeration is not possible. Thus we try to sample them uniformly using random walks on polytopes.