A Survey on Hash-Based Packet-Processing Algorithms

Sometime way back, Graham Comorde invited me to a DIMACS workshop on Algorithms for Next Generation Networks, where I talked the usual talk about hash tables, Bloom filters, and things. The organizers later had the wherewithal to undertake putting together a book or collected chapters on the topic, and asked us (us being, of course, me and my student Adam Kirsch) for a chapter related to the talk. Adam was just finishing his thesis, and was willing to take on modifying his thesis to form the basis for a survey chapter. I wrote up a section or two, and for good measure, we got George Varghese, who is the world expert -- and author of the book Network Algorithmics -- to join in as well. (In particular, we really wanted George's much more practical perspective on what works and what doesn't!) The result here is a hopefully pleasant light read on current goings-on in the area of hash-based network algorithms, attempting to blend and show the connections between theory and practice.

There's still time for feedback for the final version; please mail me if you have any constructive suggestions.

And Now, a Word from Our Sponsors (Part 2)

Continuing from last post, my trip to CA.

I visited Google and gave the CAM talk there also, where it also seemed to find a receptive crowd. (Some challenging questions arose as to whether cuckoo hashing is the right approach for hashing in software, as opposed to hardware.) Visiting Google is now like visiting a college campus, or maybe a small city. I was greeted at the parking lot by someone who directed me to valet parking. (The valet didn't seem to be there, though, so I parked myself.) I passed the volleyball courts, cafes and other places to eat, and that dinosaur on the way in; saw the gym, laundry room, doctor's office, massage area, and many many coffee-soft drink-snack bar areas; and ate at the amazing cafeteria. (The sushi line was too long, so I had to skip it. However, they did have an entire freezer full of It's It ice cream sandwiches, packaged specially with the Google logo. It's It alone is worth coming to they Bay Area for.)

I find myself without envy for the Google campus and its well-publicized perks. My limited impression was that it's too crowded and busy for me; it seems like it would be a hard place for me to concentrate get work done. I'd surely balloon up in size surrounded by open larders of food, even with the gym. I suppose I'm now just too old to enjoy the place properly, though I imagine it's fantastic for recent graduates!

The last stop on my tour was Yahoo! Research. It's always great to catch up with my "mentor" Andrei Broder, who these days always seems to be running at 110% or more. Their research group (like Google's) seems focused on Web-related algorithmics, machine learning, and this new subfield of computational advertising (I believe Andrei coined the term, in any case I like it). I talked with people about some compression-related problems, and perhaps something further will come of that.

As usual, I find myself wishing these trips could last longer. There's always too much to do and too many people to see on these visits, although that's what makes the trip interesting and fun.

And Now, a Word from Our Sponsors (Part 1)

I've just returned from a trip to Silicon Valley, where I visited Cisco, Google, and Yahoo -- all of whom have generously given me research money this year, and hence the CA visit. Besides thanking them in this blog, I thought I'd say a few things about the trip and what I saw on my brief stops at the various places. The purpose of these visits is mostly to see if I can get collaborations going, but I admit, some part of it is just giving face-time to the people and companies who have given me research money. They deserve some of my time, and I'd like to encourage them to keep providing funding!

The first stop on my trip was actually a visit to Microsoft Silicon Valley Research Lab (MSRSV). I still haven't figured out how to get research money from Microsoft, but MSRSV "started" when a lot of my colleagues at what had been DEC/Compaq/HP Systems Research Center moved en masse to Microsoft, so I have historical ties and recent collaborations with people there as well. Since my visit last year, MSRSV has moved into a very nice new building. Lots of open spaces and whiteboards everywhere. It seems wonderfully set up for group collaborations. (One very nice space for group-work, though, is a bit too close to a loud and frequently used coffee machine for my taste...) Besides catching up with everybody, Udi Wieder and others indulged me by talking about some of the many variations of trace reconstruction problems that are still open. Hopefully we'll get somewhere on some of them.

Cisco is a huge sprawling collection of buildings, and the visit there itself similarly felt chaotic. They asked me to give two talks, which caused me a bit of stress the week before the trip as I reworked some slides. I ended up talking about my work with Salil Vadhan on Why Simple Hash Functions Work (talk, paper, blog post), and gave a mini-survey covering my work with Adam Kirsch (and part with Udi Wieder) on how to use CAMs to improve cuckoo hashing (talk, various papers on my papers page). [Actually, I have a new survey article covering this stuff I'll put up shortly.] Cisco still seems very, very generally interested in hashing, and applications of hashing in network measurement and monitoring in particular. I had about 40-50 people show up for the first talk, and the second mini-survey talk was broadcast and recorded for Cisco -- about 50 people showed, and apparently more than that were also listening remotely. (Just like when I teach, and my class is taped...) They have a pretty elaborate setup for these recorded technical talks, with a room set up for guests like Steve Wozniak (who was there a couple of weeks ago) rather than me. Besides giving talks there were a lot of high-level discussions about things going on with Cisco where I might be able to collaborate usefully with them.

One thing I noticed at Cisco was a much larger number of women than usual at my talks. Perhaps EE is turning out more female graduates than CS recently, or it's somehow reflective of Cisco's hiring practices.

Visiting Cisco is always very exciting. They're a lot more short-term focused than research labs, but there is this wonderful sense that what you're talking about could become a part of the fundamental network architecture. They keep me away from details, but multiple-choice hash tables and Bloom filters seem to be standard tools in their arsenal now. I'm hoping some form of cuckoo hashing might be as well someday.

STOC 2009 Preliminary Page is Up

See here.

NSF Expeditions, Complexity

I'm glad to hear of the news that Sanjeev Arora's team at Princeton was one of the winners for the NSF Expeditions grants, working on the general theme of complexity. I think it shows that some of the public relations work our community has been doing, especially with the NSF, is paying off in concrete ways. I also think that more money for theory generally just has to be a good thing -- it's $10 million more for theory than there was before.

That being said, I'll express two concerns:

1) It's odd to see so much money for theory concentrated into such a small geographic area. I realize that was the nature of the Expeditions program, and I don't fault the proposal for it. It just strikes me as strange when the general budget for CS theory is so small to earmark such a large sum of money to this project. It feels like an over-concentration of resources in what's already a small community.

The solution to this, of course, is to get more money for the general CS theory program. And I'm sure a significant chunk of the Expeditions money will go to open DIMACS-style collaborations like workshops and other events, minimizing this concern.

2) I know it's just the nature of theory, but reading over the blurbs about the various funded Expeditions proposals, I can't help but notice that while the others seem to have some sort of statement of clear goals to take things in new directions ("hope to create a new field of computational sustainability", "It aims to create an "open" alternative to mobile ubiquitous computing and communication that can spur innovations, which will have a dramatic impact on the choices users will have in the way their data and information is computed, stored and communicated", "The project aims to develop tools and theories for molecular programming--such as programming languages and compilers--that will enable systematic design and implementation of technological and biotechnological applications that require information processing and decision-making to be embedded within and carried out by chemical processes."), the complexity grant will "hope to better understand the boundary between the tractable and the intractable" and "attack some of the deepest and hardest problems in computer science". Doesn't that sound, I don't know, just like business as usual? My concern is that it's probably important to the theory community long-term for this Expedition to have some major concrete success attributed to it at the end of the day. I have no doubt that good things will come out of this, just based on the people, who already do good work -- but will the output be the sort of things that in retrospect justify this investment?

Book by FemaleScienceProfessor

I'm an occasional reader of the blog FemaleScienceProfessor. Often the blog is just about being a science professor, which is interesting, and I can relate to. And sometimes the blog is specifically about being a female science professor, which is also interesting, even if I relate to it less.

Well, FSP has re-worked past blog entries into an on-line book available at lulu.com. I haven't yet bought and downloaded it yet, but from the Table of Contents, it appears to be a particularly worthwhile book for graduate students thinking about a life in academia, and for new faculty. The bulk of the book seems gender-neutral, if that's a concern. I thought I'd give it a free plug.

SIGCOMM 2008, Part 3

Here are a few more papers from SIGCOMM which should be of particular interest to a more theoretical audience. (Generally, SIGCOMM papers are interesting -- but again, I'm focusing here on papers that I think might be of special interest to theory people. It strikes me that I should, at some point, similarly summarize papers from a major theory conference -- like STOC 2009 -- that would be of special interest to networking people. Of course, SIGCOMM makes that easier, posting abstracts and all the papers online...)

There's a paper on analyzing BitTorrent in the game-theoretic incentive-style analysis sense. It will require a more careful reading from me, as I'm not a full-fledged game-theory/CS type researcher, but it sure looks interesting on the first perusal. I'm naturally biased to the idea that if all this current effort on game theory that is going on in computer science (and particularly in theory) is to have payoff, real-world protocols must be considered and analyzed. So in that sense, this should be a really interesting paper.

While it doesn't appear particularly theoretical (it looks like what I like to joke is a standard networking paper -- lots of pictures and tables, no equations...) this paper on spamming botnets from Microsoft includes Rina Panigrahy (well known for his work in both theory and practice) as one of the co-authors. (I figure Rina had something to do with where I saw the words "entropy reduction", but that's just a guess...)

SIGCOMM 2008, Part 2

The Accountable Internet Protocol (AIP) paper asks the question: what if we re-architectured the Internet to start with self-certifying addresses, so that there was a layer of accountability -- you'd know where packets are coming from. This paper clearly fits square in the mold of the NSF FIND program. They suggest what a self-certifying architecture would look like, how routing would work with such an architecture, consider potential attacks on the proposed architecture, and discuss whether technology trends would make such an architecture feasible. Certainly interesting, although I admit to high-level unsubstantiated concerns about the specific address architecture they propose. (I suppose as a "kid" I saw too many key-exchange-style protocol papers where a subtle flaw was exposed by a subsequent paper...)

I notice they used a Bloom filter in the paper without even giving a citation. Have Bloom filters now become so successfully widespread in the networking community that no citation is needed? What a nice thought! (Or maybe the authors just ran out of space for the citation.)

Another SIGCOMM paper continues on the path set out by for example Feigenbaum, Papadimitriou, Sami, and Shenker, on using game theory to study the behavior of BGP. They propose a more realistic model (where, for example, Autonomous Systems can be paid for attracting traffic) which, naturally, leads to more negative results in terms of the truth-telling behavior of ASes. (Why is reality so often disappointing this way?)

SIGCOMM 2008, Part 1

About a year ago, I took a look at some SIGCOMM 2007 papers. I won't be attending SIGCOMM this week, unfortunately, so in the interest of self-education, I thought I'd look at some of the papers this year. (The site currently has the papers up. Wow, what a neat idea...)

Before getting into papers, I thought I'd mention that Don Towsley is being given the ACM SIGCOMM award. This is a great choice, and well deserved. And relevant to this site's audience, Don is, in my mind, primarily a theorist. Not a FOCS/STOC theorist to be sure, but a theorist nonetheless. As the award announcement states:

Towsley, who is Distinguished Professor of Computer Science, has made innovative and pioneering contributions in developing foundational modeling and analysis techniques that have enabled a better understanding of some of the most important aspects of today's computer networks, network protocols and networked applications.

Modeling, analysis, understanding... that's what theory is all about. It's people like Don that made networking an open and understanding place for people like me. Thanks! And hooray for Don!

Now for papers. As before, I'll give brief synopses (at the level of the posted abstracts :) ), as I'm just looking at these papers on the fly. The network coding crowd has attacked again with the MIXIT system, which seems to throw together a bunch of ideas in a clever fashion to improve performance on wireless mesh networks. Recall that the basic working definition of network coding is that intermediate nodes do more than store and forward, they can process the packets as they come through (creating encoded packet variations). Here, the basic unit is not taken to be a packet, but a symbol (a small collection of bits), with symbols being packed into a packet. This allows nodes can "take apart" packets; if a whole packet doesn't come in error-free, the node can take symbols that appear to be right with high enough probability (based on information from the physical layer), and re-package (via linear combinations, a la "standard" network coding) and send on only those symbols. Because erroneous symbols might get through, an end-to-end error-correcting rateless code is also used. All of this appears to improve throughput.

The paper seems interesting -- another proof-of-concept paper for network coding in wireless systems, which is where I suspect network coding will be able to make the most inroads over the next few years. I can't tell yet how practical this really seems (without a more detailed reading), but the idea of taking apart packets and sending only the good pieces in combination with multiple coding techniques seems quite nice.

As an aside, the pdf for this paper seems to contain a picture or something that crashes my poor Mac around the 8th or 9th page. Help!

Security Issues in Cambridge

Harvard is getting new ID cards next year, thanks to an ambitious student who apparently figured out how to forge IDs (including a duplicate ID for University President Drew Faust). Because, really, how could using unencrypted ID numbers on the card, and giving access to undergraduate computer user assistants access to all ID numbers, ever lead to a problem? (The student also apparently made fake state driver licenses as well. Who says Harvard students don't learn useful real-world talents?)

Of course, Harvard isn't the only institution in Cambridge where students can obtain skills in the security area. Some MIT students, working under the famous Ron Rivest (the R of RSA!), figured out several flaws with the new ticket system for the Boston subway system, including ways to rewrite tickets so that they have lots of money available on them. So, naturally, the subway system sued to keep them from talking about the flaws at a security conference.

In both cases, the systems seem easily breakable (well, at the least the Harvard IDs were easy, not sure about the subway) with a card writer that can be obtained for a couple hundred bucks.

Of course, I'm not surprised, based on previous experience.

I wonder when organizations that want secure cards will realize that perhaps they ought to ask the students to try to break the system before they deploy it, rather than wait for them to break it after.

On Simulations

I've been coding up some simulations for some Allerton papers that are due all too soon. Of late I've depended far too much on my (now former) student Adam Kirsch to take care of doing our simulations, but he's graduated, and they're needed, so off I go. (Adam's graduating is all to the good, but clearly, I'll be missing him, especially when it comes time to write simulations.)

I'm always amazed at how averse theory people seem to be to doing simulations. I find them useful for generating ideas and thinking about problems in the early stages -- cutting off wrong directions and giving insight into the right ones. If you don't like doing simulations for such purposes, because it doesn't work for you, or you're clever enough to not need data, I have no issue with that -- people work differently.

But I also use simulations as a way of checking my work. If I have a theorem that says that a random process will behave a certain way, and it's possible to code a simulation of the process, I'll check my theorem with code. If the theory and the code don't match up, my assumption is that something is wrong somewhere, and the result is not ready until the two match or I know why they don't. Surprisingly, I think it's about 50-50 as to which I end up finding is wrong, the code or the theorem. (By the same token, if I don't have a theorem, and there's more than one way to simulate a process, I'll code multiple simulations, and make sure they match!)

Of course not all results can be checked by coding something up -- but many can. Particularly in the study of random processes, which is my area. And it's clear to me that many researchers don't check by coding -- because I (or students working with me) have several times found mistakes by doing a simple implementation and finding that we get different numbers out than the paper gives. Generally the mistakes aren't "fatal" -- usually a constant is off somewhere, and often eventually the O notation will take care of it -- but of course it is grating as a reader when something in a paper is plain wrong and you're left to figure out why. When someone doesn't do a check-by-code, I must admit, it lowers my trust of and my overall opinion of the person's work. Sure, people make mistakes (myself included) -- but if you're ignoring a straightforward approach for checking your work, that doesn't inspire confidence.

I imagine some theory people are so out of practice coding they "can't" do a simulation. (But hey, that's not really an excuse, that's what grad students are for...) And others probably just consider it a waste of time. If you really are good enough not to need to check your work this way, more power to you. Me, I'll get back to the (admitted drudgery of) coding my things up and seeing if they work the way I think they should....

The Job Market, Post Analysis

When I was in graduate school, the academic/research lab job market was pretty soft. By the time I graduated, it was a little better, but not great; you could see things heading upward, though. (Of course, I should point out here the caveat that generally the job market always seems a bit softer in theory than in anything else...)

So, looking back this last year, what is everyone's take on the job market this past year (and the trend for next year)? It seemed to me that while it's not in a completely disastrous state, it's not great, and it's been trending downward the last year or two. The effects of the economy and the long-term exodus of CS majors is not helping in academia, and while there's some availability in research labs, there doesn't seem to be a lot of spare capacity. Google is providing a much-needed outlet, as are (to a lesser extent) Yahoo Research and the new Microsoft Cambridge lab, but it's not clear (to me) how all three will play out long term, or even in the next few years. (If it weren't for sponsored search, I hesitate to think where the theory job market would be today. And if Yahoo ever does get bought out, what will happen to research...?)

There still seem to be jobs available for the best people (or, depending on your point of view, the people with the best buzz), and we still don't seem as saturated as I always hear physics and math are. But the market seems weak, and it's something students should be aware of.

I'd be happy to hear more informed opinions, or disagreeing opinions, or especially insights on the job market from non-theory people...

Problematic Students

One thing they don't warn you about in graduate school -- unless some places have changed their "teaching preparation" classes to be somewhat more useful -- is that, every once in a while, you'll get a student who is, shall we politely say, "problematic". This is the student that takes up 80% of the time you spend interacting with students that semester, and in a negative way.

I've probably seen a few more of these students than the average, because I've allowed my course to be offered through the Harvard extension school. There have definitely been many cases there of students who just enter the class insufficiently prepared, and most of them quickly drop the class. But occasionally there's one who misunderstands and thinks it's our fault (mine and the TAs) that they're failing a class that they may not have had the necessary background for to begin with. (I've recently had to deal with such a student, which brought up this line of thinking.)

For sheer annoyance value, though, my most problematic student was a Harvard student. He or she (let's use "he" from hereon) got a warning from me partway through the semester because he failed to turn in an assignment. I told him he had done fine on the assignments he had turned in, but if he didn't turn in one or more future assignments, his grade would suffer, and he could even fail the class. He said he'd understood.

After the midterm, he did not turn in another problem set. Which would be fine, except that he then made a rather large issue out of failing the class. He insisted on knowing the exact formula I used to assign grades, going over every question on the midterm and final with me, and so on. In short, he refused to take responsibility for the outcome, which is the hallmark of a problematic student.

I'm curious if other teachers have had similar experiences, and what advice they might have in dealing with such students. (My advice -- catch these students early, and document by e-mail what they have been told regarding their performance! And try to spend more time with more positive students.)

How Cuill Is It?

Having a strong interest in search engines, I woke up this morning and promptly took a look at cuill, the new search engine at www.cuill.com. I'm sure you can find 100 news articles on it if you want.

The first thing I always look for, naturally, is myself. One of the blessings of having a near-unique name is that searching for oneself is quite easy. Indeed, I'm sure that in the future everyone will be trying to have an essentially unique name, if only so they can register their name as a domain on the Internet without conflict. (Hey, I just looked up Mike Smith -- currently Dean of the Faculty of Arts and Sciences at Harvard -- and he shows up 3rd on Google for me. I'm impressed -- for such a common first-last name combo, that's pretty high up!)

Color me unimpressed with Cuill. They did put my homepage up first, with the nice picture of the cover of my book. After that, a lot of stuff from citeseer and such -- so you can quickly get titles/descriptions of some my papers, but it doesn't seem the best use of the real estate on the page. As a comparison, Cuill suggests it has 22,992 results for Mitzenmacher. Google suggests it has 63,700. While not perfect, Google will pretty quickly get you to my home page, my publications page, my blog, my book (on Amazon), my DBLP entry, and a few of my papers, which seems a better set of results than what Cuill currently gives.

A few other tests suggested what I expected (since every once in a while a new search engine pops up, and the story is often the same). It's good, but not great. It seems a little slow, but perhaps that will get better (it might be getting hit overmuch by a lot of curious people like me). But your mileage may vary, and it's always interesting when a new search engine opens up to the world.

A Reviewing Story

I'm reminded by some current goings-on about "unusual" reviews, especially one of my worst reviewing experiences ever. I'm sure most everyone has stories of some really painful, inexplicable reviews -- it's like our version of "bad beat" stories in poker -- so here's one of mine.

I had been part of a project that was looking at human-guided search techniques, and specifically we had done a lot of work on 2-D strip-packing, a common problem looked at in the OR and occasionally in the CS literature. Basically, our paper introduced what we would later generalize to Bubblesearch for this problem, and demonstrated how user interaction could lead to even better performance.

We submitted it to a journal-that-will-remain-nameless that claimed it was at the intersection of OR and CS. This seemed a fit to me. This is a standard OR problem; heuristic approaches for it have certainly appeared regularly in other OR journals. We had a very CS-oriented approach, using greedy-based heuristics, and fairly nascent techniques from the interface of AI and user interfaces. We wanted it in front of the OR audience, where human-interaction optimization systems would have been a fairly novel and potentially useful idea.

The reviewers didn't go for it (even after we revised it to answer their complaints). Clearly the human-interaction stuff was a bit beyond what they were able to cope with; if that had really been the main stated objection -- "this is really too AI/UI-ish for us to cope with," then I could have been disappointed by their lack of desire to expand their worldview and moved on. But one reviewer seemed to clearly to think we didn't properly cite and compare results with what I imagine was his own work (which included a paper that was at best tangentially related, and a paper that was apparently under review at another journal and was not publicly available in any format when we wrote ours). Another reviewer simply said that the readers of the journal wouldn't be interested. This is his summary of what we did:

"You look at a simple and natural modification of pretty much the first packing that comes to mind, an idea that could be described over the phone in two minutes, assuming no previous knowledge. Beyond that, you run a bunch of experiments and find out that you get improvements over some metaheuristic." [My note: that "some metaheurisitc" was the one giving the best published results for the problem at the time.]

Yes, that's right, all we did was introduce a painfully simple heuristic -- that hadn't appeared in the literature before, anywhere -- for a well-known, well-studied standard problem, and run experiments showing it beat the best known results on a variety of benchmark instances. I could see why that wouldn't be considered interesting to readers at the OR/CS intersection. Sigh. It's one thing when a reviewer doesn't get your work. It's another when a reviewer gets your work, seems to admit that it's quite good -- at least I view simplicity combined with performance that beats several papers worth of more complicated previous work a plus -- and just says, "But that's not interesting." How do you argue with that?**

I've shied away from the OR community since then. Being fed up at that point, we sent the paper to the Journal of Experimental Algorithmics, where I felt we'd have fewer problems, even if it wasn't exactly the target audience. If you want to read the paper and decide for yourself if the original reviews were warranted, you can find a copy here. (New Heuristic and Interactive Approaches to 2D Rectangular Strip Packing.)

**I admit, I have had to give reviews like that for conference papers -- where the review ends up being, "Sure, I think this is good, you should publish it somewhere, but I'm afraid it's just not in the top x% of the papers I'm seeing and we're space limited for the conference." I hate writing such reviews, but at least I don't make up reasons why the paper isn't good...

SWAT roundup, finally

Finally got around to putting up my slides and survey from my invited talk on open problems for deletion channels and related channels from SWAT online.

While there, Thore Husfeldt told me my idea for a "general CS book for high school students" has already been done -- in German. He gave me this link for the actual book, and another link for the notes/surveys the book was based on. Anyone know more about this project -- and if we can just translate a bunch of the chapters? (This project has not received much attention from me lately...)

Journal Policies -- IEEE/ACM Transactions on Networking

The Transactions on Networking, or ToN, is changing its policy somewhat on papers. Before, it used to be the page limit was nominally 12 pages, but you could pay $200 per extra page for up to 2 extra pages. Now, the page limit will nominally be 10 pages, and you can pay $220 per extra page up to 4 extra pages.

As I've mentioned before with Transactions on Information Theory (which is, I know, already changing its policy on correspondences), I don't understand page limits for journal articles. An article should take the space it needs for the authors to adequately express their ideas. Admittedly, for ToN, this is less of a problem than for ToIT; 14 pages is generally enough for most any networking paper. I suppose the page limit helps prevent papers with a seemingly endless series of graphs each presenting minimal information. (There are still plenty of networking papers like that, but page limits at least cut down the number of graphs that can appear.) Still, there must be some high-quality papers that authors either send elsewhere or artificially cut down to the page limit.

This change in policy, though, seems just to be a way for them to pull in some extra money. I know IEEE and its societies have had money problems in the past; maybe it's getting worse.

ToN is a high-quality journal, and has been a good outlet for some of my work. I haven't minded paying $400 in the past for the two extra pages when needed. At some point, though, there's a limit. Time for me to look closer at how Open Access journals like Theory of Computing are faring monetarily these days -- is there a networking equivalent yet?

A BIG Theory Conference

Lance talks about TCS's lack of a big conference after attending GAMES. (I recently talked about something similar with regard to ISIT.)

I'm in favor of a BIG cs theory conference, but I don't see a clear path to it. One way of doing it would be to have a mini-FCRC especially for theory, with 6+ conferences/workshops together over a weeklong period. I'd imagine there'd be some small, hopefully nominal fee to allow access to everything, and lots of administration issues. (A CD with all papers would be nice, for instance.) Some conferences have moved this way-- ICALP, for sure, and even SODA has ALENEX and ANALCO set up before it regularly -- but nobody seems to have tried to set up something like this. One possible advantage of this approach is that it could reduce the "quality control" concerns that generally arise for larger conferences.

So what would you like to see strung together into a theory-super-conference? A summer conference including SPAA, PODC, STOC, SOCG, EC, and a few other things sounds like fun to me...

ISIT this week

While many theory CS people will be spending the week at ICALP (and
adjacent workshops and such), the information theory people will be
spending the week at ISIT. No wonder these communities don't get
together as much as they should -- conferences are cross-scheduled!
CS theory will be well represented at ISIT, however, as Avi Wigderson
is one of the plenary speakers.

ISIT is bigger than, well, any theory CS conference I know, because it
is the major IT conference each year. CS theory has nothing
like it, with more, smaller conferences throughout the year, and (it
seems to me) many more specialized conferences and workshops. So here are some things I think worth observing for theory CS people, just to think about how we do things, and if we'd want to change:

1) ISIT goes for a week. One day of tutorials, 5 days of talks, with
4 parallel sessions, and a plenary each day. So naturally, most everyone
comes. (Um, no, I'm not going this year. That new baby thing...)

2) There's specific time for the Board of Governors of the IEEE
Information Society to meet and do their business. A benefit of a
conference where most everyone comes is that having "business meetings" like this seems easy to set up. Similarly, there's a large Awards Luncheon, and most people are there to pick up their awards, and see/hear the award-winners.

3) There are several activities especially for students. Roundtable
discussions, a panel led by the student committee, and a panel on
balancing career and personal life (see here and here for recent related posts on Sorelle's blog on that theme). Generally these are done over lunch, and lunch is provided for the students. (Never underestimate how well students respond to free food.)

4) Part of the tradeoff in establishing a large conference is that a higher
percentage of papers are accepted. And there's an understanding that individuals are not supposed to submit large numbers of papers, as large-scale participation is one of the goals. (This used to be explicit in the call -- something about multiple papers from an author being subject to more scrutiny -- but I don't see it in this year's call.)

As a relative outsider, I enjoy the ISIT setup. There's one
conference I know I can send my IT papers too; when I go, there's a
chance to see everyone, though there is sometimes the challenge of
tracking them down and scheduling a meet. There's a clear and strong
sense of community at the conference, despite the size.

I'm not trying to say that CS theory doesn't have a community-feeling.
But it does feel like the CS communities tend to partition themselves
more into loosely overlapping subcommunities. There's no universal
conference, although perhaps SODA (moreso than FOCS/STOC, based on sheer size) comes closest. I wonder, sometimes, what we as a community lose from this.

Zittrain on Colbert

So I'm a little late with this news (hey, I was out of the country), but Jonathan Zittrain was on Colbert plugging his book The Future of the Internet and How to Stop It. (If you Google Zittrain and Colbert, you'll find links...) It's a pretty tech-laden interview for the mainstream, in my opinion.

This is relevant (at least to me) because I've known Zittrain for years -- we interned at Microsoft at the same time back in college, and bumped into each other again at Harvard (where he was a law professor, before moving to Oxford). I'm now officially humbled -- someone I know, approximately sort-of in my field, has appeared on Colbert. (OK, I admit, I'd personally rather go on the Daily Show, but still...)