Representation Complexity of Enumeration and Counting Algorithms

• Applicant: Professor Dr. Christoph Berkholz
• Subject Area: Theoretical Computer Science
• Term: since 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 414325841

Analysing the complexity of algorithmic tasks is a core topic in theoretical computer science. For example, computational complexity provides notions of reductions to analyse the complexity of decision and counting problems in terms of the size and structure of the instance. 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 hand, 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. Another objective is the design and analysis of dynamic representations, which support efficient updates of the output representation after the instance has changed.

• DFG Programme: Independent Junior Research Groups