UB Theory Weekly – Week 20

Hi all,

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. 


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s