Dr. Christoph Berkholz

Dr. Berkholz erforscht die Komplexität von Algorithmen, die Daten aufzählen und zählen – ein Kernthema der theoretischen Informatik. Sein Fokus liegt darauf, wie schwierig solche Aufgaben je nach Struktur und Größe der Eingabedaten sind und wie man diese Schwierigkeit mathematisch nachweisen kann. Für Unternehmen und öffentliche Institutionen ist das relevant, wenn sie verstehen müssen, ob bestimmte Datenauswertungs- oder Suchalgorithmen in der Praxis machbar sind oder zu lange dauern würden. Seine Methoden helfen, algorithmische Grenzen zu identifizieren und damit bessere Entscheidungen über Softwareentwicklung und Datenverarbeitung zu treffen.

🔒 Das System hat 175 mögliche Industrie-Partner gefunden — Firmen, Scores und Begründungen sind nur für eingeloggte Nutzer:innen sichtbar. Anmelden

• NW/1: Repräsentationskomplexität in Algorithmen zum Aufzählen und Zählen

  Quelle ↗
  409-01-A · Algorithmik und Komplexität

  Die Komplexitätsanalyse algorithmischer Fragestellungen ist ein zentrales Thema der theoretischen Informatik. So liefert die Komplexitätstheorie geeignete Werkzeuge, um mittels Reduktionen die Komplexität von Entscheidungs- und Zählproblemen in Abhängigkeit von der Eingabegröße und -struktur zu untersuchen. Das Projekt befasst sich mit der Komplexität algorithmischer Fragestellungen, die – im Gegensatz zu klassischen Entscheidungsproblemen – eine Ausgabe erzeugen. Insbesondere sollen Verfahren untersucht werden, die eine kompakte Repräsentation ihrer Ausgabe berechnen. Auf der einen Seite können solche Algorithmen deutlich schneller terminieren, als die Größe ihrer Ausgabe es vorgibt. Auf der anderen Seite erlauben geeignete kompakte Repräsentationen der Ausgabe sowohl eine speichereffiziente Darstellung als auch eine effiziente Weiterverarbeitung, wie beispielsweise das Bestimmen der Ausgabegröße oder das Aufzählen der Ausgabeelemente in kurzen Intervallen. Methoden zur kompakten Repräsentation wurden seit knapp zwanzig Jahren im Bereich „knowledge compilation“ insbesondere für das Zählen und Aufzählen erfüllender Belegungen aussagenlogischer Formeln weiterentwickelt. Daran angelehnte Konzepte wurden in den letzten Jahren außerdem zur Entwicklung speicherplatzeffizienter Datenstrukturen in Constraint Solvern als auch bei der Entwicklung effizienter Mehrfach-Join Algorithmen verwendet. In diesem Projekt soll eine umfassende Theorie kompakter Repräsentationen für das Constraint Satisfaction Problem und für die Anfrageauswertung in relationalen oder probabilistischen Datenbanken entwickelt werden. Dabei sollen zum einen möglichst kompakte Repräsentationsformate entwickelt werden, die ein effizientes Weiterverarbeiten ermöglichen. Zum anderen sollen die Grenzen der effizienten Repräsentierbarkeit durch das Beweisen unterer Schranken an die Größe von Repräsentationen aufgezeigt werden. Im Bereich des Constraint Satisfaction Problems wollen wir die Struktur der Instanzen verstehen, die eine polynominell große Repräsentation der (möglicherweise exponentiell großen) Lösungsmenge erlauben. Um die Grenze effizienter Repräsentationen auszuloten, werden wir geeignete Einschränkungen, sowohl an die Constraintsprache, als auch an die Struktur des Constraintnetzwerks betrachten. Im Bereich der Datenbanktheorie wollen wir Anfrageauswertungsalgorithmen entwickeln, die gegeben eine logische Formel aus einer bestimmten Anfragesprache und eine relationale oder probabilistische Datenbank, eine kompakte Repräsentation der Ergebnisrelation erzeugen. Auch hier wollen wir passende untere Schranken an die Größe von Repräsentationen beweisen. Ein weiteres Ziel ist das Entwickeln dynamischer Repräsentationen, die es nach einer Modifikation der Eingabe ermöglichen, die Repräsentation der geänderten Ausgabe effizient anzupassen.

• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement

  2016

  Theory of Computing Systems · DOI

  An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of colour refinement is to find a stable colouring that uses a minimum number of colours. This is a widely used subroutine for graph isomorphism testing algorithms, since any automorphism needs to be colour preserving. We give an O((m + n)log n) algorithm for finding a canonical version of such a stable colouring, on graphs with n vertices and m edges. We show that no faster algorithm is possible, under some modest assumptions about the type of algorithm, which captures all known colour refinement algorithms.

• Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps

  2016

  DOI

  We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least nΩ(k / log k). Our trade-offs also apply to first-order counting logic, and by the known connection to the k-dimensional Weisfeiler--Leman algorithm imply near-optimal lower bounds on the number of refinement iterations. A key component in our proof is the hardness condensation technique recently introduced by [Razborov '16] in the context of proof complexity. We apply this method to reduce the domain size of relational structures while maintaining the quantifier depth required to distinguish them.