Projektdaten

---

Repräsentationskomplexität in Algorithmen zum Aufzählen und Zählen

---

The proposed project considers the complexity of algorithmic tasks that - in opposite to classical decision problems - generate an output. In particular, we want to analyse procedures that generate a compact representation of the output. Those algorithms can be way faster than any algorithm generating the uncompressed output. Moreover, a suitable representation of the output allows efficient postprocessing, such as computing the size of the result set or enumerating its elements with bounded delay. For propositional formulas, compact representations that allow efficient counting and enumeration of the satisfying assignments have been developed in the area of "knowledge compilation". In the last years, related concepts have been applied to develop space-efficient data structures in constraint solvers as well as efficient multi-way join algorithms. The main goal of this project is to develop a comprehensive theory of compact representations in constraint satisfaction as well as for query evaluation on relational or probabilistic databases. On the one had, we want to develop compact representation formats that allow efficient enumeration and counting. On the other hand, we want to identify the borders of efficient representability by proving lower bounds on the representation size. In constraint satisfaction we want to understand the structure of instances that admit a polynomial-size representation of the (potentially exponential-size) result set. To identify the limitations of efficient representations, we will consider appropriate restrictions on the constraint language and the structure of the constraint network. In database theory we want to develop query evaluation algorithms that, given a logic formula from a particular query language and a relational or probabilistic database, generate a compact representation of the result relation. Here we also want to prove matching lower bounds on the size of representations.