I’m really glad I don’t work with anything more dangerous than a paperclip. Also, I’m glad I don’t work in LeConte Hall.
Monthly Archives: August 2006
Three classic results on the AVC
I wrote a summary of three classical results on arbitrarily varying channels that I think make a nice story. The first is the original 1960 proof by Blackwell, Breiman, and Thomasian. The second is Ahlswede’s elimination technique. The last is the symmetrizability result of Csiszár and Narayan. Together, these three results settle some basic questions regarding arbitrarily varying channels, and I tried to make the exposition self-contained and readable by people who have had a basic course in information theory.
Macaca and George Allen
Senator George Allen (R-VA), in reference to an American-born citizen, S.R. Sidarth :
This fellow here over here with the yellow shirt, Macaca, or whatever his name is. He’s with my opponent… Lets give a welcome to Macaca, here. Welcome to America and the real world of Virginia.
This casual racism gives lie to the claims of “non-racism” made by so many people in the US. In the case of the American who has never met a person of South Asian descent, such bigoted remarks may best be explained by ignorance combined with immersion in a culture that resists difference. But for an elected representative who cannot possibly claim inexperience, it reveals a deliberate and ingrained racism that colors every decision. Maybe he hasn’t really outgrown his high school years, when he sported the confederate flag. Via TPM.
Update : Video.
Allerton, here I come
My paper, entitled Randomization for robust communication in networks, or “Brother, can you spare a bit?” has been accepted to the Forty-Fourth Annual Allerton Conference on Communication, Control, and Computing. Allerton is quite close to Urbana, which means I get to go home for a week! Hooray!
Chez Panisse
(Shattuck between Cedar and Vine) I’ve lived in Berkeley for 4 years and I finally went to Chez Panisse, the restaurant of Alice Waters that supposedly revolutionized California food. We ended up going upstairs, to the Cafe, which is more relaxed and cheaper (but not cheap by any stretch of the imagination). Liz and I split everything and we had, between us,
- 1 Bottle 2003 Catherine and Pierre Breton Bourgueil “Galichets”
- Cannard Farm cucumber, chervil, and radish salad with local albacore tuna
- Baked Sonoma goat cheese with garden lettuces
- Local king salmon baked in the wood oven with gypsy peppers, summer chanterelles, and roasted potatoes
- Hoffman Farm chicken al mattone with tomato-potato gratin, corn, and okra
- Pistachio cake with kirsch cream and blackberries
The dominant impression that I had from each of the dishes was that fresh ingredients are absolutely delicious. None of the dishes struck me as particularly amazing, but the flavor came from the ingredients. That’s one way of cooking, but the herbing and spicing came off a little dull to me. Nothing on the menu looked vaguely spicy to me.
I don’t think I’ve ever had cooked tuna that didn’t taste really fishy, but this fish was mellow, almost buttery, and the cubumbers were nice and sweet. Try as I might, I couldn’t taste the chervil, but it looked pretty. Whatever dressing they put on the garden lettuces was far too salty for my taste. The cheese came in two little rounds covered in spiced crumbs and warmed so it was gooey. Wrapping some goat cheese in the lettuce yielded little crunchy tangy packets of yumminess.
As I learned last night, “al mattone” means cooking the chicken under a brick. What we ended up with was something almost resembling fried chicken, with a crispy skin and firm but juicy meat inside. The gratin was probably one of my favorite parts of the meal — the vegetables’ sweetness complemented the slighly crunchy potatoes, and the okra was just right. The salmon was actually unremarkable, which is where the freshness really came to the fore. The only disappointing thing about this dish was the gypsy peppers, which I thought had no taste and weren’t at all spicy. Of course, I’d never heard of gypsy peppers before.
The pistachio cake was good, but remarkable only for its moistness. In restrospect I should have gotten the nectarine cobbler, but I think at the time we were both too stuffed. The wine is a keeper. I know I can get it at Kermit Lynch, so I’ll try to find it there. I know nothing about wine, so I can’t say it had spicy oaky notes or anything like that.
Will I go back? Probably, but I didn’t feel like the meal was interesting enough for me to try and go there whenever I save up enough spare cash. It was definitely good, and I’ll try and go there one or two more times before I leave.
paper a day : importance sampling in rare-event simulations
Introduction to importance sampling in rare-event simulations
Mark Denny
European Journal of Physics, 22 (2001) : 403–411
This paper is about importance sampling (IS), which a method to improve the error behavior of Monte Carlo (MC) methods. In engineering systems, getting good simulation results for rare events (such as decoding error) on the order of 10-10 would require an obscene amount of computation if you just did things the naive way. For example, the quality of a numerical bound on the tail probability of a random variable gets worse and worse as you look farther and farther out. Importance sampling is a method of reweighting the distribution to either get a smaller error in the regime of interest and/or uniformize the estimation error. This paper gives some motivation, a simple IS algorithm, analysis, and some simulations. It’s pretty readable, and I went from knowing nothing about importance sampling to getting a decent idea of how to use it in practice, along with its potential problems and benefits.
a quote that gives some comfort
From Van H. Vu’s “Concentration of Non-Lipschitz Functions and Applications,” Random Structures and Algorithms 20 : 262–316, 2002 :
Finding this hypothesis was actually the hardest part of our work, requiring some insight and a numerous number of attempts. As the reader will see after reading Section 5, a proper induction hypothesis not only allows us to derive a powerful result, but also reduces the proof to a rather routine verification of a few conditions.
I have spent a long time reading through difficult proofs with numerous lemmata, wondering why it had to be so complicated. Some things have to be proved by brute force. For others, just phrasing the problem in the right way can make the proof seem trivial. Some might say “well, I could have done that,” but the more accurate response is “I wish I had thought to do it that way.”
adventures in grant administration
I just learned the Berkeley way of doing financial support for TA’s and RA’s here. The payroll paperwork for the appointment is sent down to the Graduate Division, which up-front pays the University for tuition and fees. They then turn around and charge the department or grant per month for the money over the course of the semester. That way, if you’re an RA and get fired after one month, the Grad Division will turn around and charge you for the last 2/3 of the tuition and fees.
For those who are TA-ing this semester, the bus pass fee and student life fee are not covered by the teaching appointment, so those have to be paid out of pocket. I don’t recall this being what happened in the past, so in my mind that’s a real step back for TAs. This fee is only waived for first-year grad students, presumably to lull them into the false sense that Berkeley is a place which fully supports its graduate student instructors.
I know that these policies happen for good reasons, namely to prevent waste and trim budgets. I’m sure that similar things happen at most other universities. But the way the bureaucracy evolved seems so bizarre to me at times.
Solla Solla Enna Perumai
Via Sepia Mutiny, one of the most awesome videos I’ve ever seen — a song from the 1981 Tamil film Ellaam Inbamayam and starring the rather famous actor Kamal Haasan (or if you’re IMDB, Kamal Hassan). He was awarded the Padmashri, but I would venture to guess that this particular video is not his finest acting moment. He does, however, have what some might call “the funk.”
UPDATE : he really likes gold lame boots and vests, it seems.
paper a day : Fountain Capacity
This is one of the papers I saw at ISIT. At the time I thought I understood it, but reading the actual paper made it much clearer.
Fountain Capacity
S. Shamai, E. Telatar, and S. Verdú
Proc. Int’l Symp. on Information Theory
The background for this paper is fountain codes. The basic idea is pretty simple. Suppose you have k packets of data that you want to send. Then one way of sending them is to pick a random subset of the packets, XOR them, and send that, along with some header information about which packets are in the XOR. This is just a linear combination of the packets, so a receiver getting a sufficient number of coded packets will be able to invert the set of linear equations to get the remaining data. The encoder acts like a fountain spewing out coded packets. Suppose the packets go over an erasure channel, for which packets either arrive intact or are erased. If there are many users with varying link qualities, the ones with better links will be able to decode early and disconnect. If a user connects in the middle, they don’t lose anything from missing the “earlier” coded packets. All that matters is that each user/decoder gets enough unerased packets to enable them to decode.
The purpose of this paper is to see if and how this decoder-centric view of communication can be put on a more traditional information-theoretic (read : Shannon Theory) foundation. The idea is that the encoder will take M messages and encode them into infinitely long strings. The encoding is randomized, and the randomization is known to the decoder. The encoded symbols go through a channel, but the decoder is pay-per-view : it can only see n outputs of the channel, but it can’t control which n outputs. An adversary, without knowing which codebook is being used, picks the schedule of n outputs observed by the decoder. The probability of decoding error is then given by the worst case over subsets of n outputs. The capacity is the supremum of rates for which the decoding error can be driven to 0.
The main results of the paper are
- Randomized coding is necessary, and an infinite amount of randomness is required.
- Fountain capacity is always upper bounded by Shannon capacity.
- For stationary memoryless channels the fountain capacity is equal to the Shannon capacity.
- For channels with memory, the fountain capacity may be less than Shannon capacity.
What’s a little unsatisfying about this paper is precisely the same thing that makes it interesting — the channel model they’re using is a slippery one, so it’s difficult to see how “reasonable” it is. For example, I think the infinite randomization thing is a real drawback, but maybe the channel assumptions can be relaxed to take that away. I’m interested in this paper because it is very related to arbitrarily varying channels (AVCs), which is what my thesis will likely revolve around. There are some comments at the end which relate it to AVCs, but I should think a little bit more about the real underlying problem and how to connect it back to AVCs.
An Ergodic Walk 