Funkcialaj Ekvacioj

While poking around for some references today I took a detour through the Mathematical Reviews. I heard that Rota had written some zingers, but one of the first of his that I saw, on the Riemann-Liouville integral in the complex field contained the following comment:

Many of the results are essentially known, but this seems the best treatment in the literature, which would well justify a previous brief study of Esperanto for the interested reader.

A quick investigation shows that the paper is indeed in Esperanto!

The journal is Funkcialaj Ekvacioj, which presumably means “functional equations” in Esperanto. The entire editorial board is Japanese, and since its inception most of the contributing authors have been Japanese. The journal has been going since 1958, and they have full archives online (vol. 1-40 are free). At the beginning, they had articles in English, French, and Esperanto, with the abstract (if necessary) translated into Esperanto. That stopped as early as the 1970s (more’s the pity), and articles are just written in English, but the journal’s title remains in Esperanto.

This really made my day — maybe I should translate an article into Esperanto… except that I’d have to learn Esperanto first.

LaTeX figure repository

I’m pretty picky about figures for LaTeX documents now, and I hate having to make new figures from scratch since it takes forever. So a little while ago I got this free wiki called ThousandWords to hold figures that I had made and make them (along with relevant code) available to others. At the moment it’s pretty sparse — just a few things here and there that I put up — but it would be great to have more. In particular, right now it’s all information theory, signal processing, and networking, and there’s no reason (beyond disk space) that it can’t be more diverse.

So if any readers of this blog want to put up figures of their own for public use, let me know!

“The traveller must, of course, always be cautious of the overly broad generalisation”

George Saunders visits the UK.

But I am an American, and a paucity of data does not stop me from making sweeping, vague, conceptual statements and, if necessary, following these statements up with troops.

Furthermore, I feel confident that the discovery, by my countrymen, of the unique British delicacy called “fish and chips” would put an end to American obesity for ever.

Symphony Chorus again

I’m back in the Symphony Chorus! My reaudition was a bit harrowing, but I guess it worked out ok. I’m currently slated to sing:

  • A Mozart Journey (Michael Tilson Thomas [conductor], Jeremy Denk [piano])

    Steve Reich : Variations for Orchestra (Thursday, Saturday only)
    W.A. Mozart : A Mozart Journey (all-Mozart program)

  • John Adams’ A Flowering Tree [world premiere] (John Adams [conductor],
    Russell Thomas [tenor], Eric Owens [bass])

    John Adams : A Flowering Tree (SFS co-commission, US premiere)

    • Thursday, Mar. 1 at 8pm
    • Friday, Mar. 2 at 8pm
    • Saturday, Mar. 3 at 8pm

  • MTT and Richard Stoltzman (Michael Tilson Thomas [conductor],
    Richard Stolzman [clarinet])

    Stravinsky : Symphonies of Wind Instruments
    Stravinsky : Apollon musagète
    Takemitsu : Fantasma Cantos
    Stravinsky : Symphony of Psalms

    • Wednesday, April 11 at 8pm
    • Friday, April 13 at 8pm
    • Saturday, April 14 at 8pm

conference selectivity, publication delay, and a proposal

I should preface this post by warning any readers that these thoughts are pretty rambling and tentative. I don’t fully understand all of these issues, but they do interest me, so I find it helpful to write about them. I’m not even certain that my proposed idea here would work, but I think there seems to be some problems with the status quo that need to be addressed.

A recurrent theme in many conversations I had at ISIT was about the nature and purpose of the conference. Part of this concern stems from the stressful nature of the job market, and some from changes in the culture of the field. With regards to the former, the less selective nature of ISIT and electrical engineering conferences in general makes it difficult to evaluate the quality of work of a graduate student without being familiar with the area. Because of the incredibly long delay in journal publication, there may be no objective approval of the work by the time the student graduates. The underlying problem is that information theory is expanding and changing rapidly, and the publication and conference infrastructure hasn’t adapted to deal with the higher pace and volume of research. A lot of different arguments and proposals were thrown out there, but one that seemed to garner some interest was the foundation of a new journal for smaller results — a new Information Processing Letters, if you will.

Several people complained that ISIT was too big and that there were too many “less interesting” results. The trite answers are that the field is pretty big and that what is interesting to specialists may not be interesting to the general information theory community. If we take a comparative view, another model to look at is that of CS theory. There there are two or three very selective conferences — FOCS, STOC, and SODA. The acceptance rate for these conferences is quite low, they are single track, and all of the results presented are therefore “interesting.” Adopting such as system off the shelf misses the point of a conference like ISIT, I think.

ISIT serves several different functions that I know about. The first is to take a snapshot of the field and its progress and capture this in the proceedings. Prior to last year, the proceedings only contained a single-page extended abstract and summary of the results. The original intent that those results which were big enough would get sent to the Transactions. Another function is get sufficient funds via registration fees to pay for the transactions and the operation of the Information Theory Society. Now the proceedings are on CDROM and contain the full (5 page) papers, so many of them are (mostly) fleshed-out short papers. Finally, the conference is supposed to facilitate the contact between different research subcommunities, e.g. to get the coding people to talk to the Shannon theorists.

The first fundamental problem is that information theory has expanded as a research field — there were 4+ sessions on Network Coding alone, and those problems didn’t even exist 10 years ago. As someone told me, the flavor of the conference has shifted slowly over the years, and the incremental changes are hard to detect. The net effect is that the Transactions have become enormous and bulky — many classic papers from years ago were 10 pages, but now it’s rare to see a paper under 15-20 I bet. The conference has also become enormous and bulky, with so many parallel sessions that it’s hard to even get an idea of what is going in the field. Is this because too many papers are accepted? Perhaps. I certainly wouldn’t mind if there were about 25% fewer papers there, just so that I could see a greater percentage of what was going on. Greater selectivity would mean higher quality as well, but there are costs to that. For example, next year the conference is in Nice, and I doubt many grad students in the US would be able to just go there unless they had a paper. A lower acceptance rate would also impact the fundraising aspects.

What about the positive benefits of a low acceptance rate? Some people have argued that a low acceptance rate provides a skewed but somewhat objective measure of the quality of research done by a graduate student. That is, four solid papers at “good conferences” (in the CS sense) mean that the student has developed a solid research program. This prestige factor doesn’t hold in EE and information theory because the prestige is with journal publications, not conferences. But I noted earlier, journals take forever to publish papers, and the published papers tend to be quite long (and not because they have lots of figures). So if the burden of prestige is shifted to conferences, it might be better.

The second fundamental problem is that the pace of research is speeding up, while the venues for providing thoroughly peer-reviewed research are diminished. While all papers at ISIT are reviewed, the reviewing is somewhat uneven (I had very few reviews of my paper, while others had many). Since conferences are more about sharing the results of investigations rather than presenting the most interesting new results of the field, it’s hard to separate those ides which are going somewhere from promising directions and dead-ends, both of which may be interesting in their own right.

One solution that might work for both these problems (increased research pace and more people) would be to have more venues for journal publication. A new journal with thorough peer review and editing but an emphasis on smaller results would possibly alleviate the burden on the Transactions and speed up the pace of journal publication. The conferences could still be big, but then conference presenters with more or less polished end results could journalize those rather than waiting to included in a larger paper sent to the Transactions. It’s worth thinking about in addition to pruning down the size of ISIT a bit to avoid having 12 parallel sessions 5 years from now.

ISIT 2006 : day five

ISIT 2006 : day five

The burnout was hitting hard today, so I only saw a few talks, and some of those I can’t really say anything about since I missed parts by being late. Overall I had a good time, but it was a draining experience overall. I noticed that much of the non-student crowd spent a significant fraction of their time chatting and not in sessions, which strikes me as a wise strategy. Another wise strategy to adopt is to go to the talk with the best speaker in a given slot unless you are particularly invested in the problem being given in another slot. I went to several talks in which I hoped to learn something about a new problem and its context and often came out quite confused. Information theory is wide enough that it’s hard to understand the motivation for a lot of research, and 20 minutes isn’t enough time to give that motivation for some problems, so it’s not necessarily the speaker’s fault. Still, a good speaker can get s few bits of understanding across where a less experienced speaker might be prone to missteps.

Plenary Talk :

Prof. Gemans gave an interesting overview of the current state of computer vision research, and provided a framework and perspective that I lacked. Since he ran out of time, I never really got a good feeling for the technical part of the talk, which apparently had a connection to the liar game and other fun problems, but it did drive home the point that one has to be quite careful in applying information theory ideas willy nilly in other areas.

  • Cognitive Radio: An Information-Theoretic Perspective
    (Aleksandar Jovicic, Pramod Viswanath)

    This is a modified interference channel in which one user (the secondary) knows the message of the first user (the primary) acausally. I don’t really know how to justify this assumption, but given that, Jovicic and Viswanath solve this channel in the case where the interference-noise ratio (INR) is less than the SNR. The scheme uses dirty paper coding and so on.

  • On Jamming in the Wideband Regime (Siddharth Ray, Pierre Moulin, Muriel Medard)

    This takes the mutual-information game approach to the jamming problem — the jammer and transmitter can each choose an input distribution. The latter wishes to maximize and the former minimize the mutual information of the game. In the case of the wideband limit for Gaussian channels, the capacity-achieving bursty transmission scheme must be modified using randomization. The problem I had with this talk is that I’m not sure I understood the model correctly — how does bursty transmission fit with the inherently iid mutual information game? To me, the danger (cf Ahlswede) is that we always view transmission and information problems via the Shannon lens and so the assumptions made in the channel modeling are sometimes confusing. If nothing else, my study of AVCs has taught me that there many ways to skin a cat/problem, so I need to understand this model better.

  • Strong Consistency of the Good-Turing Estimator
    (Aaron B. Wagner, Pramod Viswanath, Sanjeev R. Kulkarni)

    The Good-Turing Estimator is a method for estimating a probability distribution without knowing the alphabet size ahead of time. For example, suppose we went on a safari and recorded the number of times we saw different animals. We don’t know how many animals there are in total, since there are some we may not have seen, but we do have an empirical measure of the animals we have seen. What is the best way of inferring the underlying probability distribution from the data, assuming they are drawn iid from that distribution? This estimator assigns a total weight to all elements that occurred k times and then evenly divides that mass among those elements. This has been proven to be unbiased, and the pre-division step is consistent. The division step can be modified to make it consistent. The interesting technique is to model the underlying data as a mixture of Poissons with a “shadow” mixing distribution. It was a pretty cool analysis, and one which I wish I had thought of, since I had tried to learn about this estimator earlier. Oh well, there are lots of good ideas in the sea…

  • Oblivious channels (Michael Langberg)

    Michael Langberg was one of the few people I didn’t know who came to my talk. I had just heard about his work before coming to ISIT so I was pretty interested in going to his talk. Unfortunately I missed the first 3 minutes, so I hope that what I understood from it wasn’t compromised. The problem he has looks very much like an AVC with state constraint — a binary channel in which the channel can flip any p-fraction of bits. The key contribution of his work is to use a new concentration inequality of Vu to derive the capacity result in a more constructive way. The approach was more from a coding theory perspective, where we want to construct a code with minimum distance 2 p n to avoid any errors. There’s a longer FOCS paper related to this and the ISIT paper still, so I have some work cut out for me.

  • Rate-Constrained Beamforming for Collaborating Hearing Aids
    (Olivier Roy, Martin Vetterli)

    This was an interesting model problem in which there are two hearing aids, one in each ear, and one can transmit to the other to do some beamforming and noise cancellation. The problem is formulated as s unidirectional source-channel communication problem with side information at the decoder, and a rate-distortion tradeoff is derived based on a spatial model of the head. It was a neat application of multi-terminal source-coding ideas to an application, but I think some more complicated models should be considered (a lossy version of Orlitsky’s problem?) before trying to commit this to an architecture.