I am pleased as punch that Katalin Marton won the 2013 Shannon Award. She made seminal contributions in information theory in the earlier years but has been active in combinatorics and stochastic processes since. Many people start doing information theory because of an interest in digital communications — my own academic background reflects this — we get some blinders on regarding the role information theory plays in other fields, such as statistics (c.f. Rissanen) and combinatorics (c.f. Ahlswede). It’s great to see Marton’s work recognized, and I hope she talks about some of her more recent interests. Finally, I find it inspirational that a woman has finally won the Shannon Award — it’s a sign of the change that is happening in engineering more broadly, I hope.
Just a few brief notes on the plenaries. Prakash Narayan gave a nice talk on his work on secrecy generation and related problems. It was nice because it tied together a number of different models in one talk so that if you were someone who had only looked at wiretap problems you could see a more unified approach to these problems. It was a little technical for my pre-breakfast brain though. Ueli Maurer gave an overview of his new approach to cryptography — I had seen a version of this before, and it was full of pictures to illustrate the reductions and interfaces he was trying to create. I think if I had more of a background in formal CS-style cryptography I might have understood it a bit better. It feels like trying to build a different style of bridge between theory (formal reasoning about security) and practice.
Abbas El Gamal gave a rather personal Shannon Lecture, taking us through a number of stages in his research life, together with some perspectives on his new book with Young-Han Kim on network information theory. He ended by calling for the IT community to really go and tackle new problems and develop new tools and models to do that. One of the things that came across more sharply for me in this ISIT, partly due to the Cover memorial, is that information theory really is a research community. Of course, there are groups and cliques and politics and problems, but each ISIT is a real coming together that reinforces that sense of community. That’s valuable.
Since I am getting increasingly delayed by post-ISIT and pre-SPCOM business, I am going to have to keep the rest of blogging about ISIT a little short. This post will mention some talks, and I’ll keep the other stuff for a (final) post.
Efficient Tracking of Large Classes of Experts
András György, Tamas Linder, Gabor Lugosi
This paper was on expanding the reference class against one is competing in a “prediction with experts” problem. Instead of doing well against the best expert chosen in hindsight, you compete against the best meta-expert which can switch between the existing experts. This leads to a transition diagram that is kind of complicated, but they propose a unifying approach which traces along branches — the key is that every transition path can be well approximated, so the space of possibilities one is tracking will not blow up tremendously.
Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing
David Donoho, Adel Javanmard, Andrea Montanari
What a trendy title! Basically this problem looks at the compressed sensing problem when the sensing matrix is banded (this is what spatially coupled means), and solves it using Bayesian approximate message passing to do progressive decoding and elimination. The optimality is in the sense of matching with the Renyi dimension of the signal class for the data. I alas did not take notes for the next talk, which also seemed related: Hybrid Generalized Approximate Message Passing with Applications to Structured Sparsity (Sundeep Rangan, Alyson Fletcher, Vivek Goyal, Philip Schniter)
Quantized Stochastic Belief Propagation: Efficient Message-Passing for Continuous State Spaces
Nima Noorshams, Martin Wainwright
This problem was on BP when the state space is continuous — instead of passing the whole belief distribution, nodes pass along samples from the distribution and the receiving node does a kind of interpolation/estimate of the density. They show that this process converges on trees. This is related to a problem I’ve been thinking about for decentralized inference, but with a different approach.
Ueli Maurer, Björn Tackmann
This was a cool talk on a framework for thinking about synchrony in clocks — the model is pretty formal, and it’s something I never really think about but it seemed like a fun way to think about these problems. Basically they want to formalize how you can take a given clock (a sequence of ticks) and convert it into another clock. The goal is to not throw out too many ticks (which equals slowdown), while achieving synchrony.
Non-coherent Network Coding: An Arbitrarily Varying Channel Approach
Mahdi Jafari Siavoshani, Shenghao Yang, Raymond Yeung
Of course I have to go to a talk with AVC in the title. This looks at the same operator channel for network coding but then they assume the network matrix may be arbitrarily varying (with known rank). In this model they can define all the usual AVC concepts and they get similar sorts of results that you see for AVCs, like dichotomies between deterministic coding with average error and randomized coding.
Alternating Markov Chains for Distribution Estimation in the Presence of Errors
Farzad Farnoud, Narayana Prasad Santhanam, Olgica Milenkovic
This talk was on the repetition channel and getting the redundancy of alternating patterns. They show upper and lower bounds. The idea is you start out with a word like abccd and it goes through a repetition channel to get aaabbcccdddd for example, and then you look instead at abcd by merging repeated letters.
On Optimal Two Sample Homogeneity Tests for Finite Alphabets
A two-sample test means you have two strings and and you want to know if they are from the same distribution. He looked at the weak convergence of the asymptotically optimal test to get bounds on the false alarm probability.
Hypothesis testing via a comparator
This was on a model where two nodes get to observe and drawn i.i.d. from either or and they separately compress their observations into messages and . The decision rule is to decide if . What’s the best exponent?
The Supermarket Game
Jiaming Xu, Bruce Hajek
This was on queuing. Customers come in and sample the loads of queues and then pick one to join. Their strategies may differ, so there is a game between the customers and this can affect the distribution of queue sizes. As a flavor of the weird stuff that can happen, suppose all customers but one only sample one queue and join that queue. Then the remaining customer will experience less delay if they sample two and join the shorter one. However, if all but one sample two and join the shorter one, then it’s better for her to sample just one. At least, that’s how I understood it. I’m not really a queueing guy.
At ISIT 2012, there were posters up for a site called ShareRI.org: Share Research Ideas, an initiative of a student at UIUC named Quan Geng. It’s a platform for posting and discussing papers — sort of like creating a mini-forum around ArXiV posts. It seems to be just starting out now, but I figured I would post the link to see if others take it up. I imagine as things scale up it might run into similar problems as Wikipedia with trolling etc, but it’s an interesting idea which has come up before in discussions with the IT Society Online Committee, for example.
Muriel Medard said that the IT Society is only 1% of the IEEE. All you other Electrical Engineers : you are the 99%!
ETA : Only 0.1% become Fellows! We are the 99.9%!
I am at MIT for ISIT 2012. All of the sessions are in the the student center (W20) and in Kresge, so I am having serious flashbacks to my days of doing theater as an undergrad. Also some vague flashbacks to sneaking into sessions at ISIT 1998. I think I saw Jack Wolf give a great talk on group testing in W20-407 back then.
The program feels pretty packed this year – 9 parallel sessions! I will blog about some of the talks, but as usual I may not be super timely. Perhaps there is a Twitter hashtag for ISIT, but honestly, how many information theorists use Twitter?
If you’re attending ISIT then you probably got an email about Trailhead, a graphical system which links papers at ISIT “based on how many authors they have in common in the references, and each paper is linked to the 4 closest neighbors.” It’s written by Jonas Arnfred, a student at EPFL. The search feature doesn’t seem to be working, but it’s a fun little app.
I wonder how different the graph would look using something like the Toronto Paper Matching System, which is used by NIPS and ICML to match papers to reviewers. One could even imagine a profiler which would help you pick out papers which would be interesting to you — you could upload 10 papers of your own or that you find interesting, and it could re-visualize the conference through that viewpoint.
I was interested in the 19 papers which had no connections. Here are a few, randomly sampled:
- Fish et al., Delay-Doppler Channel Estimation with Almost Linear Complexity
- Song and İs ̧can, Network Coding for the Broadcast Rayleigh Fading Channel with Feedback
- Bilal et al., Extensions of -Additive Self-Dual Codes Preserving Their Properties
- Bernal-Buitrago and Simón, Partial Permutation Decoding for Abelian Codes
- Kovalev and Pryadko, Improved quantum hypergraph-product LDPC codes
- Price and Woodruff, Applications of the Shannon-Hartley Theorem to Data Streams and Sparse Recovery
- Willems, Constrained Probability
- Nowak and Kays, On Matching Short LDPC Codes with Spectrally-Efficient Modulation
They seem to run the gamut, topic wise, but I think one would be hard-pressed to find many unlinked multi-user information theory papers.
On the other side, there’s a little cluster of quantum information theory papers which all have similar citations, unsurprisingly. They show up as a little clique-ish thing on the bottom right in my rendering (it may be random).
Who are my neighbors in the graph?
- Strong Secrecy in Compound Broadcast Channels with Confidential Messages — Rafael F. Wyrembelski, Holger Boche
- Lossy Source-Channel Communication over a Phase-Incoherent Interference Relay Channel — H. Ebrahimzadeh Saffar, M. Badiei Khuzani and P. Mitran
- Shannon Entropy Convergence Results in the Countable Infinite Case — Jorge Silva, Patricio Parada
- Non-adaptive Group Testing: Explicit bounds and novel algorithms — Chun Lam Chan, Sidharth Jaggi, Venkatesh Saligrama, Samar Agnihotri
- Non-coherent Network Coding: An Arbitrarily Varying Channel Approach — Mahdi Jafari Siavoshani, Shenghao Yang, Raymond Yeung