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. 

UB Theory Weekly – Week 19

Hi all,

The 19th 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 – An informal talk by Michael Wehar on the wonderful summer that he spent at IBM Research!🙂

2:50 – 3:00 pm  – Socializing with the Theory community. 

UB Theory Weekly – Week 18

Hi all,

The 18th Theory Weekly Meeting will happen this Friday between 4:00 – 5:00 pm at 203 Davis Hall(Theory Lab). The schedule will be as follows :

4:00 – 4:50 pm – A talk by me:). The abstract of the talk is as follows –

Consider the problem where we have to design two lines for a railway network: one must be a passenger line (where the train stops at all stations) and the other an express one (where the trains stops only at popular stations). This should be done in such a way that one can travel between any pair of stations using a combination of these two lines.

Does this hint a broader problem? Does this remind you of something in NYC (if you have visited there)? Does this convey a beautiful structure? To know the answers, please stop by the talk!

4:50 – 5:00 pm  – Socializing with the Theory community. 

UB Theory Weekly – Week 16

Hi all,

The sixteenth Theory Weekly Meeting will happen this Friday between 4:00 – 5:00 pm at 203 Davis Hall(Theory Lab). The schedule will be as follows :

4:00 – 4:50 pm – The continuation of the talk series by Marco Gaboardi. This will be the final installment and will center around Differential Privacy like his earlier talks.

4:50 – 5:00 pm  – Socializing with the Theory community. 

UB Theory Weekly – Week 15

Hi all,

The fifteenth Theory Weekly Meeting will happen this Friday between 4:00 – 5:00 pm at 203 Davis Hall(Theory Lab). The schedule will be as follows :

4:00 – 4:50 pm – The continuation of the talk series by Marco Gaboardi. This is the second installment and it will be on re-proving Differential Privacy guarantees for two interesting algorithms by using probabilistic coupling.

4:50 – 5:00 pm  – Socializing with the Theory community. 

UB Theory Weekly – Week 14

Hi all,

The 14th Theory Weekly Meeting will happen this Friday between 4:00 – 5:00 pm at 203 Davis Hall(Theory Lab). The schedule will be as follows :

4:00 – 4:50 pm – A talk by Sidharth Jaggi.

4:50 – 5:00 pm  – Socializing with the Theory community. 

Speaker Bio: Dr. Sidharth Jaggi received his Bachelor of Technology degree from the Indian Institute of Technology in 2000, and his Master of Science and Ph.D. degrees from the California institute of Technology in 2001 and 2006 respectively, all in electrical engineering. He was awarded the Caltech Division of Engineering Fellowship 2001-’02, and the Microsoft Research Fellowship for the years 2002-’04. He interned at Microsoft Research, (Redmond, WA, USA) in the summers of 2002-’03 and engaged in research on network coding. He spent 2006 as a Postdoctoral Associate at the Laboratory of Information and Decision Systems at the Massachusetts Institute of Technology. He joined the Department of Information Engineering, the Chinese University of Hong Kong in 2007. Sidharth’s research interests are in the realm of network coding and network error-correcting algorithms, coding theory, steganography, group testing and compressive sensing.

 

UB Theory Weekly – Week 13

Hi all,

The thirteenth Theory Weekly Meeting will happen this Friday between 4:00 – 5:00 pm at 203 Davis Hall(Theory Lab). The schedule will be as follows :

4:00 – 4:50 pm – A talk by Marco Gaboardi. The talk will be in two parts. In the first part, he will be giving an overview of Differential Privacy.

4:50 – 5:00 pm  – Socializing with the Theory community.