Today, we had two EE talks which require substantial background knowledge on communication that i don't have.....:( so I didn't follow much.
I guess tomorrow will be much better since we will have CS talks!
We also had a poster session this afternoon and there were like twenty posters there.
Among those, I want to mention one that is about a very interesting problem, the index coding problem. It is a network coding type problem but the formulation is much cleaner.
The problem describes like this. The source have a {0,1} string X of length n.
There are a bunch of receiver r_i. Each r_i is particular interested in knowing the x_i (th) bit of X. Each r_i also (already) knows a subset of bits of X (this is called the side information).
Find a coding scheme, such that each r_i will know the x_i bit of X and the source broadcasts as few bits as possible ("broadcast" means everybody can hear it).
For a motivating example, suppose each r_i knows X except the x_i(th) bit.
Then the source only need to broadcast the parity of X (number of 1's in X) which takes only 1 bits).
The facinating part of the problem is that the optimal coding scheme can be charaterized by a rank minimization problem on the adjacency matrix of the "side information graph" and also quite related the shannon capacity of a graph and also has similar type of sanwich property.
Refer to this paper for even more interesting details.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment