The 20th Theory Weekly Meeting will happen this Friday between 2:00 – 3:00 pm at 203 Davis Hall(Theory Lab). The schedule will be as follows :
2:00 – 2:50 pm – A talk by me. This is a talk that I gave earlier this year at the PCMI Research Program 2016. The talk will (most likely) span over two weekly meetings. The abstract of the talk is as follows:
The Natural Join Query (NJQ hereon) is a well-studied problem in Database Theory literature. We, in this work, observe how NJQ behaves under Hamming Distance Constraints. We look at both the algorithmic and combinatorial versions of the resulting problem. From an algorithmic standpoint, we are interested in observing how quickly the Natural Join can be computed, given only the input schema and an uniform upper bound on the table sizes. In particular, we are interested in the resulting table sizes of all NJQs under this constraint. On the combinatorial side, we are interested in worst-case size bounds for NJQs under this constraint.
We have two main results in this paper for the case when the NJQ is a simple graph:
1. We develop polynomial time algorithms that will compute the Join given only the input schema and a uniform upper bound on the table sizes under Hamming Distance constraints.
2. We explicitly prove that our NJQ bounds are tight with a constant factor, under Hamming Distance constraints.
2:50 – 3:00 pm – Socializing with the Theory community.