Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Liebe Kolleginnen und Kollegen,

am Dienstag, den 29.07.2025 um 14:30 Uhr (s.t.) wird
Harry Vinall-Smeeth einen Vortrag zum Thema

"How Small Can You Go: Lower Bounds on Representations in Knowledge Compilation, Finite Model Theory, and Beyond"

halten. Mit diesem Vortrag möchte er Ihnen die Ergebnisse seiner Dissertation vorstellen, die er in Kürze einreichen wird (Abstract siehe unten). Betreuer der Promotion ist Prof. Christoph Berkholz (ehem. HU Berlin; jetzt TU Ilmenau).

Alle Interessierten sind herzlich eingeladen!

Der Vortrag findet digital über Zoom statt, mit folgenden Zugangsdaten:

******
Prof. Dr. Nicole Schweikardt is inviting you to a scheduled HU-Zoom meeting.

Topic: PhD Talk, Harry Vinall-Smeeth, 29.07.25

Join Zoom Meeting
https://hu-berlin.zoom-x.de/j/61838684866?pwd=NkczLy9ZUFBMVXNtdmkrZ0tZYU8zdz09

Meeting ID: 618 3868 4866
Password: 638019
******

PhD Talk by Harry Vinall-Smeeth

Title: How Small Can You Go: Lower Bounds on Representations in Knowledge Compilation, Finite Model Theory, and Beyond

Abstract: In this talk, I will survey the main results obtained during my PhD. These results span a wide range of sub-areas of theoretical computer science, including database theory, finite model theory, formal language theory and knowledge compilation. What they have in common is that they concern representations, i.e., using one object to encode another.  This is a core task in computer science. For example, computers run algorithms on a wide range of objects, but to do this, we have to represent (encode) these objects as binary strings. Very often, we have a large number of possible representations of a given object. Given this, how should we choose a representation?

There are two key properties we would like our representations to achieve.  First, they should be as succinct as possible. Second, we should be able to run algorithms on them efficiently. Often these two aspects---which we call succinctness and algorithmic power---are in tension with one another. Mapping out this tension is a core aim of the work carried out during my PhD.

We will apply this lens of succinctness versus algorithmic power to a wide range of scenarios. The concrete questions we tackle include: When does the answer to a join query admit a small representation? How much more succinct can context-free grammars be compared to their unambiguous variant? What can we say about the succinctness of finite variable fragments of first-order logic? My main contributions are (often tight) lower bound results which map out the limits of various representation formats.