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
#
UB Theory Weekly

## UB Theory Weekly – Week 27

**Coding Theory in the Era of Distributed Storage Systems**
## UB Theory Weekly – Week 26

## UB Theory Weekly – Week 25

## UB Theory Weekly – Week 23

## UB Theory Weekly – Week 20

## UB Theory Weekly – Week 19

## UB Theory Weekly – Week 18

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

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

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

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