Bugs

In a recent review of a journal paper, I got the following comment:

In explaining why you are presenting simulation results, you say, "First we wish to check our theoretical analysis..." I don't understand this motivation. Your theoretical analysis is substantiated by mathematical proofs. What more evidence do you need of its validity?

Please keep this statement in mind.

I've stated frequently that theorists should actually implement their algorithms. I have some further recent anecdotal evidence to back up this claim.

I have students working on a variety of projects, and recently, I've had a strange convergence: in several of the projects, the students have found what appear to be non-trivial errors in recent theory papers (2 in CS theory, 1 in EE theory). It's not clear that any of the results actually break -- indeed, I don't think any of them do. I don't want to exaggerate. In one of them, a constant factor seems to be messed up -- not disastrous, but it is an important constant factor in context. And perhaps in one of the papers we could chalk it up to really just a sequence of confusing typos rather than an actual error.

Now I'm not naive enough to expect conference papers (or even journal papers) without errors. But the key here is that these errors were either easily found and/or proven to me by the students by having them implement the algorithms described in the paper. Then they sort of jumped out.

Implementing your own algorithm is a good way of checking your work. If you aren't implementing your algorithm, arguably you're skipping a key step in checking your results. Why should a reviewer go to the trouble of checking your work carefully if you're not?

Moreover, imagine not some student but an actual real systems-builder who decides your algorithm is worth implementing for their system. Imagine how they feel when they find things don't quite work as you've stated. That doesn't exactly inspire confidence, and is the sort of thing that discourages someone from using your algorithm. More globally, it gives systems people the feeling that theory (and theorists) aren't important. Why should they be debugging your proofs? You should give them evidence your algorithm can be implemented and works as claimed by actually implementing it if possible or reasonable to do so.

I'm not stating that you personally have to implement your algorithm. Hire a student to do it! It's good experience for them. You can apply for an REU, or other student research funding.

So, to answer the anonymous reviewer, I think there's always plenty of good reason to check our mathematical proofs by experiment and impelementation, and it's suitable to put those results in the journal paper as an aid to the reader (and reviewer!).

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.

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?

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!

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....

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...

Yet Another Survey... Deletion Codes

Next week I'll be at SWAT for an invited talk. When I gave them a choice of topics, they went with: A Survey of Results for Deletion Channels and Related Synchronization Channels. I've actually given this talk a few other places, but there's been some new stuff, so it's been updated a bit. (I'll put the latest version of the slides up on my talks page after the talk...)

The invitation gave me an excuse to buckle down and finish something I started over a year ago -- a survey article on results for the capacity of the deletion channel (and related problems) to go with the talk. I must be out of practice writing, because it's taken me most of the month to get this thing done. (Well, OK, there was that whole "baby incident" that took up some time, but still, I've clearly been doing far too much administration this last year, and I need to shake off the rust.) It's probably still a bit rough so anyone interested enough to read it, please feel free to mail corrections/suggestions directly.

Apparently, based on some mild teasing from a colleague and friend, I'm known as someone who writes survey articles. (The teasing was perhaps I'm known only as someone who writes survey articles...) I don't know why I end up writing them -- I can't really say it's a fun exercise to write a survey, though it is often educational -- but somehow I feel it's valuable. In this case, there's definitely the motivation that I've done a lot of work in this area, and I want to both promote the area and my work. The survey has a couple of dozen open problems spelled out right there, so let that be motivation for some of you to read it...

Also, I'm open on suggestions on where to publish it. My last few surveys have nicely been able to go to Internet Mathematics (see here for Bloom filters and here for power laws/lognormal distributions-- although the "uncensored" version of the power law survey from my publications page is more fun) so that they've had a worthwhile permanent home. This survey won't quite fit there, and I think it's good for such things to have a visible outlet (besides, say, arxiv). Ostensibly Transactions on Information Theory will take surveys, although I haven't seen that much in practice; and this survey doesn't really fit in the Foundations and Trends model. (I like the Foundations and Trends model, but it seems to me their surveys are like "mini-textbooks" -- and cost accordingly -- while my surveys are more like "here's some background, big ideas, and pointers to papers" -- and I'd like them to be essentially free.)

An Improved Analysis for "Why Simple Hash Functions Work"

I recently had a paper with Salil Vahdan (in SODA 2008) explaining why simple hash functions "work" for so many stream-related problems where data is hashed to be placed in a hash table or a Bloom filter or a similar structure. Here "work" means "behave essentially the way you would predict if the hash function was perfectly random." The basic reason, we suggested, was that if the data in the stream had enough randomness, it would combine with the randomness from the choice of hash function to produce value that looked independent and uniform.

Our analysis of how much randomness the data needed to have seemed a little loose. Salil and his student, Kai-Min Chung, have recently improved the analysis; here's the arxiv link, the paper will be appearing in RANDOM '08. There's some really nice and somewhat subtle arguments that I imagine will find some uses in other areas. While it "only" improves the constant factor (in terms of number of bits of randomness needed), this is certainly a case where constant factors are important.

The result further reinforces my belief that this is the right high-order explanation for why, whenever anyone actually does an experiment involving hashing, you get the right results no matter what hash function you use.

More Robust Cuckoo Hashing (ESA paper)

I have a paper at ESA, with Adam Kirsch and Udi Wieder, entitled "More Robust Hashing: Cuckoo Hashing with a Stash." (Here's an extended preprint version.) The starting point of the paper is that cuckoo hashing is wonderful, and everybody should know about it and use it. (If you don't know about it or use it, see here or here. But basically, cuckoo hashing is multiple choice hashing with the added bonus of getting to move items around among their multiple choices as needed to balance load on-line.)

So, of course, we want to make cuckoo hashing even better. And one of the problems of cuckoo hashing is that it "fails" with non-trivial probability. For example, in standard 2-choice cuckoo hashing, putting n items into 2(1+eps)n cells with at most 1 item per cell can be done with probability 1 - Theta(1/n). That gives a Theta(1/n) "failure" rate, which doesn't mean anything in terms of "average" behavior, because it can always be handled by re-hashing everything with a new hash function, so that's the end of the story in most theory papers.

In practice, that kind of failure rate is a bit high. Re-hashing an entire hash table could just be too expensive an operation to have occur that frequently for many applications. Can we improve the failure rate somehow?

Let's look at where that Theta(1/n) failure rate comes from. When there are 2 choices per item, the simplest type of failure one might imagine is that 3 items try to use the same two cells -- that is, 3 items have the same 2 choices of location. Indeed, such a problem occurs with probability Theta(1/n) [exercise LTR]. But when such a problem occurs, we can imagine taking one of those 3 items and stashing it somewhere -- in a stash as suggested by the paper title. The stash should be a little space on the side, that we may have to check whenever we look for something. If we implement a stash, how does the size of the stash affect the failure rate?

If failures were essentially independent, so that each item "fails" independently with probability proportional to 1/n^2, then we'd expect f failed items with probability proportional to O(n^{-f}). This turns out to be the right intuition; 0ur analysis shows that a stash sized for s items (for constant s) reduces the failure rate to O(n^{-s-1}). The analysis is a bit trickier, since of course item failures aren't independent, but the result seems natural.

So a small, constant-sized hash -- easily implementable in software or hardware -- reduces the failure probability dramatically, allowing one to avoid rehashing in practice. What I found particularly interesting from the theory+practice perspective is the power in this setting of a constant-sized stash. It's a very natural addition for practitioners -- I don't think it would cause an engineer to blink -- but I think it really changes the potential for cuckoo hashing, making it a structure you could imagine employing on devices used by millions of customers, without having to worry about this otherwise far-too-common failure mode.

We show similar results for multiple cuckoo hashing variations. (The analysis, unfortunately, is different for all of the variations; it would be nice for someone to develop a cleaner, nicer, more unified analysis of all the varieties of cuckoo hashing.) The case of 2 choices is of non-trivial interest, however, since Udi, along with Moni Naor and Gil Segev, have recently shown that 2-choice cuckoo hashing can be used to develop a very efficient history-independent hash table (check out Udi's web page for the paper). The main problem with such a structure is, naturally, the non-trivial probability of rehashing, which can be avoided using a stash.

The stash idea also fits nicely with my previous paper with Adam on the Power of One Move for cuckoo hashing style schemes, although there the stashes (with suggested implementation as Content Addressable Memories in hardware) were larger than constant-sized. I'm beginning to think the idea of stashes (or CAMs) should be a standard section in practically oriented hashing related papers.

A Bubblesearch (Semi-)Success Story

A colleague was backing up files to DVDs and wanted to know a good bin-packing heuristic. I pointed him to First-Fit-Decreasing and Best-Fit-Decreasing, nicely described the Wikipedia entry on bin-packing, but suggested as long as he was doing that he ought to try Bubblesearch as well. Recall Bubblesearch just tries random perturbations of the greedy ordering, to try to find a better solution; the full description is in this paper.

His reported results are that with FFD everything fit into 5 DVDs, which was the minimum necessary; but he did find that Bubblesearch improved the utilization of the first 4 DVDs from 94% to 99% (with about 10,000 random perturbations, and some small parameter tuning), which he thought was impressive.

Your mileage my vary, and I'm sure there are better specific heuristics for bin-packing. The point behind Bubblesearch is that it is a natural extension for a wide class of Greedy heuristics, and moreover is really easy to understand and to implement. My completely self-interested and biased opinion is that it (or something like it) should be taught in all undergraduate algorithms classes....

Jennifer Rexford's take on "Practical Theory"

Jennifer Rexford, who I've mentioned before is a networking person who appreciates theory, gave me a rumor that she'll be giving a talk at STOC on "networking questions relevant to the theoretical CS community." I don't see the program up yet, but I hope it's true. She's a great speaker, with excellent perspective. Kudos to those who thought to invite her!!!

She also pointed me to an editorial she wrote on her ten favorite "practical theory" papers. Naturally, I enjoyed reading her perspective. Particularly since her perspective included my name (flattery, indeed, will you get you everywhere-- or at least on my blog).

I think, however, her editorial offers several lessons. Here's my top two. First, her notion of a theory paper is a little different than ours. Most of the papers are by networking people who think mathematically and theoretically (Varghese, Towsley) or more attuned to what I think of as EE theory. This first lesson is a reaffirmation of my long-standing notion that the FOCS/STOC view of theory is, in many respects, rather limited, especially to our peers outside of theory. I think a second related lesson goes to the importance of theory people getting out there and making their work more accessible to non-theorists. In my case, that has meant writing survey articles, giving talks for general audiences and not just theorists, and going to networking conferences to talk about my work. I'm sure there's plenty of other "mainstream theory" work that Jennifer and others from networking would greatly appreciate -- if only we as a community did a bit better job of letting them know about it.

Why are You Doing Research (and the CRA blog)

Despite the last round of budget horrors, the CRA is optimistic about 2009. While I'd like to believe it, I'll believe it when I see it. The other good news is CDI seems to be going forward roughly as planned.

In an effort to spur further comments, I'll have to say I was disappointed by the discussion that accompanied my last pointer to the CRA blog. It seems we have a lot of self-deprecating sorts in our field who don't think what we do is important enough to be funded by the government. Even after the great successes of the last 20 years, many of which have ties both direct and indirect to government funding. I don't get it.

In my opinion, government's most important role is to do things for its citizens that individuals can't do adequately by themselves. That's why national defense is a government job. And so is basic research. Basic research is important for national defense, as well as for the economy -- both in national defense terms (the bigger/better our economy, the better our national defense), as well as for feeding the homeless (unless we keep moving forward and developing, there's going to be a lot more homeless to feed). For those who think that feeding/caring for the poor is more important than funding basic research, I'd ask 1) isn't it more efficient for charities/local organizations rather than the national government to do this (except in extreme, Katrina-like circumstances) and 2) where do you think the economic advancement that will keep the country going (so your kids aren't hungry or homeless) is going to come from?

Some comments were of the form "there are so many other things to be funded, why fund us?" (Let's say us means "computer science", though one could make the case for basic science more generally.) First, our success record is pretty darn good. (I'm confused by people who don't recognize that -- as if none of the work we've done has had an impact on the world.) Second, all the other sciences are becoming more computational; I believe Chazelle's riff that algorithms will increasingly become the language of science. Funding us should help all the sciences. Third, well, see the above paragraph.

So (and remember, following recent comments, I'm aiming to be "controversial" and "less nice"), I'll end on the following thought. Certainly, I do research because I enjoy it and am reasonably successful at it. But if I thought it wasn't actually important, I'd either go find a job that paid a lot more, or go find a job that I thought meant a lot more. I've known people that have done each of those. For those of you who really, honestly feel that CS research is mostly a waste -- and are still working in the area -- why are you still around?

Hunting for Problems

An anonymous commenter asked:

What advice do you give to graduate students hunting for problems?

I'd advise the following, though your working style may differ:

1. Read a lot. Nobody else wants their paper proceedings anymore, so keep those hefty tomes lying around and start reading from 2008 backwards whenever you can. I found problems (including my thesis topic) in graduate school just by reading proceedings and thinking hard when I thought I saw how to do something better. At worst, reading through proceedings introduces you to techniques, ideas, and problems, so it won't be a waste. Two notes about this approach: you'll probably have to read at least 40-50 papers before you find even one with a problem that appeals to you and that you have an idea on, and the problems you tend to find this way are generally incremental -- after all, they're based on somebody else's paper! For a beginning graduate student (with lots of time, and where publishing something incremental is just fine), those negatives aren't too bad.
2. Go to talks. For the same reason you should read a lot -- for exposure to problems and ideas.
3. Talk to people. Don't just talk to your advisor. Find other people with interesting problems and research, and see if you can help them, or if by talking to them you get a new idea for a research direction. I certainly don't come up with all of my own problems. Sharing ideas with others is key. In fact, I strongly recommend you talk with your other graduate students as much as possible, and try to start a paper-reading group/research group with them. Other students have more time than your advisor, so leverage that and work together to solve a problem. (Thank goodness we work in a field where cooperation is considered a virtue and collaboration is the norm.) At worst, it will make your work/social life at graduate school much better and less isolated.
4. Don't limit yourself to reading papers by/going to talks by/talking to theorists. If you're looking to come up with a new problem, odds are the motivation for that problem will come from outside the theory community itself. Find out what kinds of problems the systems people are having, and see if you can turn it into a theory problem. Even if your theory version is too toy to solve the real-world problem, you'll have a reasonable motivation for your introduction. And if your theory problem actually helps solve their real-world systems problem, bonus -- you now have contacts/letter-writers from outside theory that can help you in the future. And again, it will make your work/social life at graduate school better and less isolated if you talk to other people in the department besides theorists.
   

That's the top-of-my-head advice.

Distributed Beam-forming: New Preprint

Besides NSF proposals, another item that took up time over my winter non-break was finishing a submission to ISIT 2008. To me, this paper was another example of how CS theory people and EE theory people are often tackling the same sort of problems, just in a different language.

The paper is titled Distributed Beamforming with Binary Signaling. Here's the English version of the problem. A bunch of weak transmitters are trying to transmit the same message to a receiver. Before sending the message, they are all out of phase, so their signals potentially cancel each other. They'd like to send so that they are all mostly in phase, so the signals reinforce each other and the message gets through. Initially, nobody knows their phase. The only communication possible is all the transmitters can send a signal, and the receiver can broadcast information back. How quickly can alignment occur?

To better understand the problem, we simplified it as follows. In each round, each transmitter can send a bit, a -1 or +1. Suppose the jth transmitter send the bit b(i,j) in the ith round. The jth transmitter has, for all time, a fixed phase p(j), which is +1 or -1. The receiver's obtained signal in the ith round is |sum_j b(i,j)p(j)|. If there are n transmitters, we'd like to get the obtained signal to beta n for some constant 0 < beta < 1 as quickly as possible; this is what we'll mean by alignment. The system is fully distributed, so transmitters can't communicate directly, and the only feedback they get is 1 bit broadcast every round. In this simple model, we looked at lower bounds and algorithms. The lower and upper bounds are both linear in n, but trying to get those constant factors right is apparently pretty important.

While this is a natural EE theory-type problem, it feels close to very similar problems in communication complexity, at least when simplified in this way. It was also interesting working on a lower bound, where we developed a reduction from a standard rate distortion problem. It seems to me EE people don't generally think in terms of reductions, at least not the way CS people do, although it's a terminology and framework that I think is increasing in use at conferences like ISIT. On the other hand, CS people don't always do reductions that give specific constant factors (in this case, related to entropy). So all in all it was an interesting reduction to develop here.

The "full paper" (ISIT papers are limited to 5 pages) will cover a lot more variations and have more details, though I expect there will still be many open problems. More generally, the theme of unifying the "communication complexity" picture between EE and CS, much as the coding theory picture has been greatly unified of late, seems like a great place to look for research problems.

Graham/Rexford talk on GENI/CCC

The CRA has the slides for a presentation by Susan Graham and Jennifer Rexford at the Grace Hopper Conference: Introducing the Computing Community Consortium. It's a nice talk covering the CCC, GENI, and some of Jennifer's current research.

Page Limits on Journal Papers

I know of at least two journals that I publish in that have page limits on the length of papers. I am completely puzzled by this. A journal paper should be as long as it needs to be to derive and explain the results the author intends to convey, since the paper should be the final record on that piece of research. Some papers might need 20 pages; others might be too long even at 10. A hard rule of say 12 pages maximum just doesn't make sense.

I can imagine two reasons for instituting page limits on journal papers: paper costs, and reviewer time. Neither seems particularly compelling to me. Are there other reasons I'm missing? (Notice that both of these are more compelling in the case of conferences, where I would agree page limits make more sense. And even in that setting, papers costs is rapidly disappearing as a reason, and at some point, the question of page limits should probably be reconsidered.)

I do admit that there are many papers where the author should be forced to edit things down further, and most authors have a tendency to write too much rather than too little. But it seems the right answer to this is to have good reviewers and a good editor firmly tell an author that the paper is not yet ready and needs further editing. A page limit doesn't adequately solve this problem and raises new, more unpleasant ones.

Anyone want to defend this practice? Or at least suggest reasons for it I haven't thought of?

New Book : Algorithmic Game Theory

I recently received my "desk copy" of the new book Algorithmic Game Theory, edited by Nisan, Roughgarden, Tardos, and Vazirani.

While I haven't read it cover-to-cover yet, I'm very impressed by the book. It's taken a large area with a fairly short history, and broken it up into reasonable-sized chunks each written by an expert, with most chunks covering a new and active research area. For example, Michael Kearns writes about Graphical Games, Christos Papadimitriou explains the complexity of finding Nash equilibria, Jon Kleinberg discusses cascading behavior in networks and the corresponding economic issues, Ramesh Johari and David Parkes and Joan Feigenbaum and so many others have chapters on their specialties, and so on. Overall I count 45 contributors! The result is a solid tome that really combines breadth and depth to create a resource that I assume works well for people working in the area and is certainly useful for an outsider trying to look in and see what's going on. There are also exercises in some chapters; it could certainly be used as a textbook.

I'd like to see other books of this form, built up by a coalition of experts to cover emerging areas. You do lose something with this approach -- for example, many concepts are defined multiple times in various chapters, and while the authors have made an effort pointing out relations among chapters, you don't really have the sense of coherence you get from most textbooks or books about research written by a single author. On the other hand, you do get a much broader coverage of topics than you'd probably see from a single-author textbook, and I assume that it was easier to spread the workload among authors. It's not clear to me any single author (or group of 3-4) could have put something like this together in any reasonable amount of time. Kudos to the editors (and authors).

What other topics could benefit from a treatment like this?

Harry Lewis's book, Excellence Without a Soul

Since my colleague Harry Lewis is kind enough to stop by and post comments from time to time, I would be remiss not to encourage everyone with an interest in the education of college students -- in the broad sense of whether universities are and how universities should be teaching students to become adults -- to pick up his book Excellence Without a Soul: How a Great University Forgot Education (also now available in paperback as well). I highly recommend the book, and plan to give it to my daughters to read when they're teenagers so they're better prepared for the college experience.

The book takes a stark look at the directions of modern college education, painting a picture of increasing directionlessness at the leading research universities, using Harvard and Harry's experience as Dean of Harvard college as a backdrop. Whether you agree with it or not -- and I have to admit I found a strong resonance with most of the issues in the book -- it is definite food for thought, well-reasoned and well-argued through and through.

There are two very small points of criticism I can make with the book. The first is that while the book sheds light on a number of challenging problems, it frustratingly offers little advice in the way of solutions. However, I think this was quite intentional. Indeed, one of the points in the book is that for many of these problems, what is needed isn't a "solution", but leadership, discussion, and the building of a consensus within the university.

The second nitpick is that one issue raised repeatedly in the book is the invasion of the consumer culture in education. Students pay a great deal for an education, particularly at private institutions, and they expect to get what they pay for; Harry argues forcefully that this trend is not good for the education of students. It would seem to me that this should be another compelling reason why Harvard shouldn't charge for tuition, as it might lessen the "I paid for this" attitude of many students (and parents), but perhaps Harry believes that even if there was no tuition, the consumer attitude would remain.

The simplest insertion/deletion channel

The simplest binary insertion/deletion channel that I can think of is the following: with probability p, each bit independently results in two copies of itself. This is a special case of a subclass of channels that I have dubbed sticky channels, which are like sticky keyboards: each symbol can result in a random number of copies of that symbol.

Sticky channels have the nice property that contiguous blocks of (resp 1s) at the input correspond to contiguous blocks of 0s (resp 1s) at the output. This property makes sticky channels easier than more general insertion/deletion channels.

I've just had a paper on sticky channels accepted to Transactions on Information Theory; here's a link to a preprint. The main result is that for that simplest channel above, I can numerically obtain very tight bounds on the channel capacity. But of course I'd still like to know -- is there a simple formula that gives the capacity as a function of p? And is there are simple and efficient coding scheme that nearly reaches the capacity?