Group:Grad-student Theory Lunch
Title: Distance Oracle; Analog Adversary for Wireless Communication;Extreme Figures Ins
Speaker: Tiancheng Lou, Hongyi Yao, Kai Jin Tsinghua university
Time: 2010-04-15 12:00-2010-04-15 13:30
Venue: FIT 1-222


Presenter: Tiancheng Lou

Distance oracle

Thorup and Zwick[TZ05] coined the term distance oracle, which is a data structure that, after preprocessing a graph G=(V,E), allows for efficient(approximate) distance and shortest path queries. Formally, an distance oracle for a class of graphs G consists of a data structure S and a query algorithm with the following characteristics:

(1) The preprocessing time is the worst-case time required to construct the data structure for any G.

(2) The space complexity refers to the worst-case size of the data structure for any G.

(3) The query time is the worst-case time required to compute the shortest-path distance between any two vertices.

These a few weeks, we're working on the exact distance oracle on planar graph. We want to find a linear-space data structure using we can answer distance queries for planar graphs rather efficiently in time proportional to the diameter. For planar graphs with diameters bounded by O(sqrt(n)).

The main idea of our algorithm is as following:

(1) Find a tree-decomposition of the planar graph, such that, the size of each bag in the tree is not exceed O(d), where d is the diameter of the graph.

(2) Build an intersection tree.

(3) Call LCA-oracle to compute the shortest path.

Currently, we have a problem that the size of bags may be very large. We're still working on it now.


Presenter: HongYi Yao

Title: Analog adversary for wireless communication

We consider wireless point-to-point communication with analog adversarial error. To be concrete, let X be the source signal arrived at the receiver, and A be the adversarial signal arrived at the receiver. Both X and A can be characterized as dimension-n vectors over real field, with L-2 norms no more than Sx and Sa respectively.

The receiver receives X+A and desires to decode X. For the Byzantine adversary case, the problem is as hard as sphere packing, not a easy problem. For the computationally bounded adversary case, we hope to find a polynomial time encoding and decoing algorithm.


Presenter: Kai Jin

I will talk about two major problems. Extreme Figures Inscribed on Convex Polygon Problem and Multi-pattern Penney-ante Problem.

On the first problem, I will introduce some results of finding smallest similar inscribed triangle and finding largest area Parallelogram inscribed on convex polygon. On the second problem, the problem is like: Given a generic alphabet A, a probability distribution pA on A, and several distinct patterns P1, P2, ..., Pt A+. A memory-less source generate a string with characters in A according to the distribution. It stops as soon as one of the given patterns occurs. We call the occurred pattern wins. Your task is to calculate the expected stopping time of the generating process and the winning probabilities for each pattern.

There is a beautiful linear time algorithm using generating functions by Guibas and Odlyzko. I give a fundamentally different and more intuitive algorithm for this problem which is also linear time. The framework of my algorithm based on a Markov-chain model by solving a system of linear equations which is a natural thing to do. It is interesting and non-trivial to solve this system in linear time.


Short Bio: