Hi all,

The 27th Theory Weekly Meeting will happen **this Friday (i.e tomorrow)** between 4**:00 – 5:00 pm**** **at **203 Davis Hall (Theory Lab)**. I will give the following talk:

**Coding Theory in the Era of Distributed Storage Systems**

Skip to content
# Code for Food

## UB Theory Weekly – Week 27

**Coding Theory in the Era of Distributed Storage Systems**
## If Sita visits Krishna’s abode?

## UB Theory Weekly – Week 26

## UB Theory Weekly – Week 25

## UB Theory Weekly – Week 24

## UB Theory Weekly – Week 23

## UB Theory Weekly – Week 20

Random Thoughts

Hi all,

The 27th Theory Weekly Meeting will happen **this Friday (i.e tomorrow)** between 4**:00 – 5:00 pm**** **at **203 Davis Hall (Theory Lab)**. I will give the following talk:

The problem of designing error-correcting codes for Distributed Storage Systems has received a lot of attention lately. The focus of this talk will be two broad topics that cover a good subset of the literature in this area:

1. Codes with Local Repair Property: I will start with the idea of ‘Locality’ and talk about the progress in this area with recent results by Gopalan et al.

2. Codes with Exact Repair Property: I will start by motivating the idea of ‘Exact Repair’ followed by describing recent results in this area by Ye-Barg and Guruswami et al.

I will also present simple constructions in both the regimes. The first few minutes of the talk will be an introduction to Coding Theory in general.

Advertisements

The 1996 movie ‘Gokulathil Seethai’ explored this intriguing question in a fairly convincing way. In this post, let me draw your attention to an extraordinary musical moment in it — ‘Gokulathu Kanna’.

At a high level, this song considers the scenario in the title. Nila (Suvalakshmi) is the stand-in for Sita and wonders what she is doing in Gokulam (actually referring to Rishi’s (Karthik) house). By the second stanza, she describes Rishi’s womanizing and drinking habits (with a secret admiration for him). Let’s pause for a moment on these two lines:

போதையிலே நின்றானவன்

பூஜைக்கின்று வந்தானவன்

This is the exact time when Rishi enters the frame of the celebration and guess what? He is carrying a glass of alcohol (a perfect sync!).

Rishi then launches onto the next stanza and now it is obvious that he has feelings for Nila. But still there is an air of indecisiveness, which is cleared when Manivannan (playing Rishi’s dad) launches into the next stanza. In particular, he asks him to leave all his bad habits (see the following lines), reassuring that Sita is the right one for him.

கோகுலத்து கண்ணா கண்ணா

லீலை விடுவாயா

கோகுலத்தில் சீதை வந்தால்

நீயும் வருவாயா

Overall, this song shows us three things:

- Nila’s respect and admiration for Rishi, hinting that it could turn into love.
- Rishi’s feelings for Nila and his indecisiveness, since he is portrayed as a Man-Child.
- Manivannan’s approval for Nila and Rishi’s togetherness.

This, indeed is the crux of the movie (from what-we-saw-so-far to what-we-will-see) and is causally tossed off as yet another song. Unsurprisingly, this is what makes this song endlessly fascinating to analyze!

Hi all,

The 26th 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 – 3:00 pm **– A talk by Chaowen Guan. The abstract of this talk in his words:

This talk will be demonstrating the connection between the complexity of evaluating polynomials and integer factorization, which was first done by Lipton. We will show a more general result by highlighting the importance of of a global bound on sufficiently many distinct roots of the polynomial. In particular, we can derive tradeoffs between the randomized complexity of factoring and the number of distinct roots. At last, we will also show what could the actual ”defenses” of factoring against efficient attacks.

Hi all,

The 25th 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 – 3:00 pm **– A talk by Oliver Kennedy. The abstract of this talk in his words:

Over the years, the database community has developed a range of semantics for coping with uncertainty (ambiguity, conflicts, and/or incompleteness) in data. After introducing the space, Oliver will outline several of these semantics, including both data models, query processing semantics, and their embeddings into classical relational query processing. Oliver will also discuss a query-rewriting technique that ‘virtualizes’ uncertainty, making it possible to vary the complexity of query processing, allowing simpler representations of uncertain results to be generated more efficiently. Finally, Oliver will show how this technique is used in the Mimir probabilistic query processing system.

Warning: This talk will not include any novel complexity results or formal proofs… and you may be subjected to one or more graphs.

Hi all,

The 24th 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 – 3:00 pm **– A talk by Shi Li on his recent FOCS 2016 paper: **Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions**.

Hi all,

The 23rd 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 Michael Langberg. The abstract in her words:

Can one bit of added communication significantly change the amount for information one can communicate over a noisy network? In this talk I will introduce and discuss this question. Hopefully, I will be able to show the (surprising?) results of a recent work on the topic.

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.** **