I have been hanging out mostly at the network coding sessions. For those who haven't seen the term, the one sentence description of network coding is that you combine routing with coding -- intermediate nodes do not just store and forward, they get to evaluate functions of received packets and send those on as needed. Why aren't there more CS theory people working on network coding (myself included!)? It's a huge relatively new area in information theory and networking. There are lots of interesting, challenging open problems. Lots more info here. Also, there's a Scientific American article this month by three of the leaders in the field -- Michelle Effros, Ralf Koetter, and Muriel Medard (three top names in information theory that CS people should become familiar with if they are not...) -- that gives excellent high-level background.
The most interesting talk so far was the work by Koetter and Kschischang, which reduces network coding with erasure and errors to an interesting coding variant. In this setting, codewords are vector subspaces; erasures delete a basis vector from the subspace and errors add a spurious basis vector to the subspace. What do codes in this world look like? (Hopefully I'm doing the question some justice -- it was a great talk.)
Michael Luby and Amin Shokrollahi won the IEEE Eric E. Sumner Award "For bridging mathematics, internet design, and mobile broadcasting as well as successful standardization." Go Digital Fountain.
I gave a talk on good codes for limited insertion/deletion channels.
At the lunch, I talked with some people about how the information theory community doesn't really have a "competitive" conference -- like a FOCS/STOC, or a SIGCOMM. They were wondering about how to and the impact of adding one. I suggested adding special single-track sessions (as opposed to the eight parallel sessions) for the key papers to ISIT.
Subscribe to:
Post Comments (Atom)
5 comments:
Thanks for talking about ISIT! As a student of communications and info. th. it is personally interesting to read what someone in CS has to say about it!
A bunch of CS theory people have
looked at network coding and written
several papers. The authors include
Moses Charikar, Kamal Jain, Lap Chi Lau, Bobby Kleinberg, Nick Harvey, April and Eric Lehman, David Karger,
Petr Sanders, myself etc (names in no particular order and I am sure I am
forgetting others). I think some of
the high level interesting
questions have hit
technical hurdles and the CS people are naturally a little less invested in the area to push the agenda beyond a point.
Michael, it's also nice to hear that you come to visit UCL on Friday. Don't forget to post about that. :)
Chandra,
I didn't mean to suggest nobody in CS theory had worked in network coding. But it's been very sparse. At ISIT, there are multiple sessions per day on the subject, and it was the subject of one of the tutorials. A huge difference...
Michael,
You say "There are lots of interesting, challenging open problems." I know maybe 2-3 problems that I find interesting and challenging (e.g., the conjecture of Li-Li (and independently due to others) about the advantage of network coding over routing in certain undirected network problems). The list of papers at the website you linked to is too big, and it's difficult for someone not working in the area to find useful papers. May I suggest a short survey of the main results and problems in the area as a possible topic for this blog?
Post a Comment