Invited Talks

Alessio Conte:
Proximity search: foundations, advancements and (current) limits

Florent Capelli:
Geometric Amortization of Enumeration Algorithm

The class of enumeration problems having a polynomial delay algorithm is often regarded as the class of "easy" enumeration problems. From the definition of polynomial delay, it seems that the most interesting property of such algorithms is the guarantee that one can get a new solution by waiting only a polynomial amount of time after the last output. In many scenarios however, it is enough to have a guarantee that for every t, the time needed to output t solutions is linear in t and polynomial in the input size. More formally, we are interested in enumeration algorithms having the following property: on input of size n, for every t, after a time t*poly(n), the algorithm has output at least t solutions. We say that such algorithms have an incremental linear delay.

Nofar Carmeli:
Enumeration and Related Problems in Query Answering:

When analyzing the complexity of answering queries over databases, the traditional approach asks for the total time required to compute all answers. As the number of answers may be much larger than the size of the input database, there has been a focus on analyzing this task from an enumeration point of view, i.e. bounding the delay between successive answers when they are returned one by one. The motivation here is that we can get value from seeing some of the answers before all of them are produced. A more recent shift takes this approach a step forward. Depending on the final goal of the query, we can save a significant amount of computation by solving enumeration-related problems that do not produce the entire solution set. As an example,  simulating random access to a sorted list of query answers can be used to efficiently compute quantiles of the query answers. This talk will inspect enumeration-related problems in databases from a fine-grained complexity point of view and discuss their connection to enumeration.

Torsten Mütze:
Combinatorial generation via permutation languages

Abstract: In this talk I present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations. This framework provides a unified view on several known Gray codes and yields many new ones, and it exploits and establishes several deep connections between reconfiguration graphs, posets and polytopes. The talk gives an overview over the main concepts and applications of our framework, and it is based on joint work with Jean  Cardinal (UL Bruxelles), Liz Hartung (MCLA), Hung P. Hoang (ETH Zurich), Arturo Merino (TU Berlin), and Aaron Williams (Williams College).

Contributed Talks

• George Manoussakis    Efficient maximal cliques enumeration in weakly closed graphs    
• Mohammed Elaroussi, Lhouari Nourine, Mohammed Said Radjef and Simon Vilmin    On the preferred extensions of argumentation frameworks: bijections with naive sets
• Mengze Qian and Ryuhei Uehara    Efficient Enumeration of Non-isomorphic Block-Cutpoint Trees   
• Yann Strozecki    Space complexity of enumeration
  
• Christian Bean, Émile Nadeau, Jay Pantone and Henning Ulfarsson    Using Combinatorial Exploration to sample permutations
• Caroline Brosse, Arnaud Mary and Vincent Limouzy    Polynomial delay algorithm for minimal chordal completions
• Antoine Amarilli and Mikaël Monet    Enumerating Regular Languages in Constant Delay
• Stefan Neubert    Enumeration in P
• Yudai Enomoto, Kawakami Yuki, Kazuhisa Seto, Takashi Horiyama and Jun Mitani    Counting and ZDD-based Enumeration of Locally Flat-Foldable Box-Pleated Crease Patterns on the 45-Degree Grid System
• Shin-Ichi Minato, Mutsunori Banbara, Takashi Horiyama, Jun Kawahara, Ichigaku Takigawa and Yutaro Yamaguchi    A ZDD-Based Method for Exactly Enumerating All Lower-Cost Solutions of Combinatorial Problems
• Karl Bringmann, Nofar Carmeli and Stefan Mengel    Tight Fine-Grained Bounds for Direct Access on Join Queries
• Yasuaki Kobayashi, Kazuhiro Kurita and Kunihiro Wasa    Polynomial-Delay and Polynomial-Space Enumeration of Large Maximal Matchings

Abstracts of the papers are available for registered participants on this page.