joint work with Tomasz Gogacz

Speaker(s)

Szymon Toruńczyk

Affiliation

Uniwersytet Warszawski

Date

June 15, 2016, 2:15 p.m.

Room

room 5870

Title in Polish

Entropy Bounds for Conjunctive Queries

Seminar

Seminar Automata Theory

---

We study the problem of finding the worst-case size of the
result Q(D) of a fixed conjunctive query Q applied to a
database D satisfying given functional dependencies. We
provide a characterization of this bound in terms of
entropy vectors, and in terms of finite groups.
Our result shows that the problem of computing the
worst-case size bound, in the general case, is closely
related to difficult problems from information theory.

---