Sunday, October 07, 2012

Allerton Panel

This year was the 50th Annual Allerton Conference on Communication, Control, and Computing (website).  Hard to believe it's been around that long.  I think my first year there was 1999, and while I haven't gone every year, I've been to Allerton regularly since.  

I happily got to be the token (theoretical) computer scientist on one of the panels, where one of the questions was specifically whether the interaction between communications/control and theoretical computer science had been healthy. I found it interesting that two co-panelists Alexander Vardy and Muriel Medard both had opinions very similar to mine.  If you looked about 10-15 years ago, you might have been very optimistic about what I'll call the "theoretical electrical engineering" community and the "theoretical computer science" community coming together in a big way.  There had been some significant successes -- specifically, in the Guruswami-Sudan work on list decoding, and work on low-density parity-check coding (including the paper by Luby-Mitzenmacher-Shokrollahi-Spielman).  Codes were clearly becoming important on the complexity side in TCS, and algorithmic considerations were becoming more important in TEE.  

And while there's been the occasional crossover subject since then -- people on both sides of the aisle work on network coding, though it still seems more clearly a TEE subject than a TCS subject, and compressed sensing and even social networks have taken hold in both TEE and TCS -- there's still surprisingly little interaction between the two communities, especially since, more and more, I think the two communities are growing ever closer intellectually.  (I tried to spin some fun thoughts on that during the panel -- TEE sprung from Shannon, focusing on communication and transmission rate;  TCS sprung from Turing, focusing on computation and computational complexity.  And for fifty years or so, the two subjects have carved out fairly distinct sets of problems.  But as the distinction between "communication" and "computation" continues to fall away, the sets of problems the two groups work on get ever closer together.) 

Culturally, however, TEE and TCS seem quite different, not just with different conferences and journals, but different ideas about measuring research and publications.  (Conferences don't really count for TEE, while journals don't really count for TCS.)  Perhaps this inertia keeps the two communities apart.  Or perhaps there's something else that I'm missing, but several younger people after the panel came up to me afterwards and seemed to agree.  They wanted to be able to move back and forth between the communities, as the problems they were interested in seemed relevant to both (and possibly or probably needed techniques from both to fully tackle the problems), but the divide between them seemed rather large, and the best way forward career-wise seemed to be to stick with one or the other.  

So the panelists seemed to agree with their sense of mild disappointment that the past decade hadn't really lived up to its potential in terms of TCS and TEE combining forces to meet their intellectual challenges, but still remaining optimistic that there were opportunities there.  

I'm told the recording of the panel will go on line at some point;  I'll link to it when it is.  


AC said...

Two things:

1. There's been a *lot* of followup work in TCS since Guruswami-Sudan on that space of problems, as I'm sure you know. Has it got TEE people working in that space (not a rhetorical question)?

2. In the other direction, TCS has had at least one major thing to contribute to TEE: the notion of "Information complexity" (Chakrabarti-Shi-Wirth-Yao '01, BarYossef-Jayram-Kumar-Sivakumar '02, Barak-Braverman-Chen-Rao '10). But I'm not sure we've done a good job of publicizing this idea to that community. Well, I try once a year at ITA, but the impact feels limited.

-Amit C

Grigory Yaroslavtsev said...

+1 to Amit's second point. To some extent, communication complexity seems to have been in the intersection of interests of both communities.
Information complexity view of communication complexity made it much more Shannon-like, which might be of interest for the TEE community.

Anonymous said...

"... journals don't really count for TCS."

Maybe in the USA, but here (Europe) I think journals count for a lot, although of course conferences are very important. People around me care a lot about having their work actually peer-reviewed (i.e. checked line by line), instead of what happens when you submit to a conference.

Michael Mitzenmacher said...

AC: I think there's been at least as much (probably more) work by TEE people on list decoding since Guruswami-Sudan as TCS people, although the focus tends to be different.

AC+GY: I agree communication complexity should be a point of intersection (I think I mentioned it in the panel), though it hasn't really seemed to take hold in TEE.

Dan Spielman said...

I would have thought that the different views of conferences in the two communities would help people move between the two: it means that you can present work in both FOCS/STOC and Allerton/ISIT.

Anonymous said...

Slightly off topic and probably discussed many times before at various blogs, but I'd like to ditto the first anonymous. Even though conferences are obviously important, for many purposes journals are more important in the UK; e.g. fellowships (from various funding bodies) across sciences, or REF (research excellence framework; used to be call RAE), to which every academic submits his or hers top 4 pubs and universities get funded based on this list.

Michael Mitzenmacher said...

@Dan -- in theory one can publish in both conferences. But it doesn't happen in practice. Theorists aren't motivated to present their results in Allerton, and Allerton people aren't motivated to publish in FOCS/STOC -- they are discounted from a "real" publication in their respective communities. Moreover, there are different formats and other issues to deal with -- why do the extra work? (For a while the Allerton people managed to corral some theorists to present their work at Allerton, but that seems to have died down again.)