Disconnecting from E-Mail

One nice thing about traveling to New Zealand was that I spent several days disconnected from e-mail. I went a whole 80+hours without checking my mail on both ends of the trip. It was nice. (I could have checked mail, but in New Zealand it seems like all the hotels make you pay for Internet access. I didn't feel like paying. Of course, I had e-mail available at the workshop.)

The experience has suggested to me that I ought to try moving to limit my e-mail during the day. It seems more productive to set aside time to specifically deal with e-mail; maybe first thing in the morning and last thing before leaving the office. I'm not sure how this would work with other people, though; many people treat e-mail like it's a phone call, an immediate connection (including my wife), when of course it's not. I often see "emergencies" pop up in my e-mail box; while I was gone, I was asked to call somewhere for my opinion of a job candidate, and an NSF director wanted me to expand on my research nugget (as usual, by yesterday preferred, by tomorrow would be OK). These people didn't need to get in contact with me that second, but there seemed to be the clear expectation that I'd see their message and move on it within a small number of hours. Is that a realistic expectation?

Of course, these weren't real emergencies, and making a practice of leaving e-mail aside and blocking my e-mail time better would probably increase my efficiency, and possibly my happiness, since I would feel less that I was constantly being interrupted.

Practical Graph Isomorphism

Continuing my efforts to prove I was not just sitting out by the pool in New Zealand, I'll mention a highlight of the talks of Brendan McKay (of the Australian National University). Brendan has written code for graph isomorphism called nauty that works quite well in practice, handling graphs with up to millions of nodes. So while the complexity of the graph isomorphism problem is not known, it can be pretty hard to come up with bad examples that are actually hard to solve. As someone who's happy with good heuristics, I found it quite amusing to watch it in action. (On the other hand, it seems that many of the ideas behind this program are "old" by computer science standards. Are there any competing programs/approaches out there? Seems like a possible research direction. to revisit the algorithm engineering for this problem...)

While settling whether graph isomorphism is in P would certainly be interesting, Brendan pointed out that the question of whether it is in coNP is also quite important. Are there polynomial-sized certificates that can be used to prove that two graphs are not isomorphic? And one can imagine in practice one would like to have some methodology for easily convincing someone that two graphs aren't isomorphic.

As Brendan is a co-editor-in-chief of the Electronic Journal of Combinatorics, we also talked a bit at lunch about electronic journals (in particular the EJC). The EJC continues to grow successfully. (I'm happy to say I've published in it, back in 2004.) Remember to support your electronic journals.

Voting and Anti-Voting

While at NZIMA, I listened to Dominic Welsh's talks on Markov chains. It was a general talk, with a large chunk devoted to rapid mixing and applications. At some point he brought up the voter and anti-voter model, problems that I heard about a long time ago in the distant past, and that raised some questions in my mind.

The voter model can be expressed as follows. We have an undirected graph G, where each vertex has a label. For convenience, let's assume the labels are in {0,1}, although larger alphabets are possible. At each time step, a vertex x is chosen uniformly at random, and x chooses a neighbor y uniformly at random. Then x changes its label to match y's label. This is a Markov chain with absorbing states with all vertices having the same label. It's natural to ask things like what is the probability that you end up in the all 0/all 1 state from a given configuration.

If the graph is d-regular, and you start in a state with k 0's and n-k 1's, a simple argument gives that the probability of eventually being absorbed into the all 0 case is k/n. (Exercise Left To Reader.) Things seem to get more complicated for more general graphs. Here are some interesting questions that come to mind. Note: I don't know which are open and which aren't...

1. Given a graph G and a starting configuration of labels, is there a polynomial time algorithm for computing the probability of being absorbed into the all 0 state? Or could a hardness result be proved? [My guess is there's a hardness result in there somewhere.]
   
2. Given a star graph (one node in the center, connected to n-1 other vertices) and a starting configuration, what is the probability of being absorbed into the all 0 state (preferably in some natural closed form)? In particular, if you start with a 1 in the middle and a 0 everywhere else, what is this probability as a function of n? Notice that by symmetry here one can easily compute these values in polynomial time; the question is whether there are pleasant equations. [On some reflection, it's clear there will be nice equations; this is almost a birth-death chain with an added "phase" needed to track the center vertex. Exercise left to reader...]
   
3. Similar questions to 1/2, but ask about the expected time/distribution of time until absorption.

Perhaps more interesting is the anti-voter model, which works just like the voter model, except that x changes its label to disagree with y's label. (Here the {0,1} alphabet is the most sensible.) Now we do not have absorbing states; we have a stationary distribution. But again one can ask similar questions:

1. Given a graph G and a configuration of labels, is there a polynomial time algorithm for compute the stationary probability for that state?
2. Are there natural families of graphs for which the stationary distribution for the anti-voting model has an easily expressible form? [d-regularity no longer seems to be enough...]
   

Obviously, one can argue about the importance of these questions, but I would just take the point of view that such easily expressible and seemingly natural questions about basic Markov chains are always interesting in their own right.

New Zealand (NZIMA)

For the last week, I've been at a workshop in New Zealand, sponsored by the New Zealand Institute of Mathematics and Its Applications. They're having a programme in algorithms, including this workshop, and they invited me to give a couple of talks. (I'll be giving versions of my "Brief History of Power Laws" talk and my "Bloom Filters Survey" talk.)

OK, OK, I know, this violates my "avoid-travel" rule. Occasionally, I find myself suckered into travel for various reasons. In this case, the managed to time the workshop over my kids' winter break, in the middle of Boston winter (and the end of New Zealand summer), while it's winter. (My wife, also a native Californian, does not enjoy winter.) Besides the weather motivation, I've never been to New Zealand, and don't see a lot of future opportunities. So why not?

I'm happy to say we've had a really nice time in New Zealand, and I encourage visitors. Let me advertise that there will be a similar workshop sometime at the end of 2008 here as well. Perhaps if you're interested you might contact Mark Wilson, who will also leave comments with pointers and information. And the rest of the week I'll have some notes/ideas/open problems from the week in New Zealand.

Service and the NSF

I recently returned from an NSF (National Science Foundation) review panel. (Of course, I'm not allowed to say when, or for what.) On the way back, at the airport, I ran into a more senior colleague (from an entirely different field -- not EECS) coming back on the same flight. It came up that he had never served on an NSF review panel. He admittedly seemed a bit sheepish about it, but offered the excuse that there were more important things to do, and I will give him the benefit of the doubt and assume that he meant other service activities, not research and such. Essentially, his argument seemed to be that NSF panels were a waste of his time.

Having served on a half dozen or so NSF review panels, I have some sympathy for this point of view. In particular, being anti-travel, I'm not sure why we have to fly in for a two-day meeting to make decisions; it's expensive for the NSF and time-consuming for me. (It's not clear to me that decisions are any better because of the face-to-face meeting. Indeed, arguably, they can be worse, depending on the group interaction. But government process is government process, so unlike for PCs, not having the face-to-face meeting is not currently an option...)

However, despite the time, I've tried to make myself available when the calls for NSF panels go out, because I've always figured that if the NSF is paying my summer salary (which, in large part, they do), they have the right to ask for some of my time. Indeed, my gut reaction (without working through the arguments) is that it's objectionable that they don't actually require people who have received funding to serve on a review panel at some point during the term of their grant, though I suppose the implementation of that rule could become unpleasant. In short, my moral interpretation is that by taking their money, I'm part of their system, so when they come calling, I should respond, even without an explicit quid pro quo.

Even if one does not subscribe to this implicit understanding, I think it's important for us individually and as a community (including non-academics who don't get NSF funding directly) to do our service for the NSF, particularly in the way of review panels. In general, citizens should be keeping an eye out on how the government uses their money, and in this specific case, as scientists, we should be paying especially close attention to how the government is distributing research money to scientists in our own and related fields, and we should be attempting to influence the process to move in the right directions as much as possible. The panels give us some opportunity to influence the process, and these otherwise near-useless face-to-face meetings give us some opportunity to influence the NSF administrators who shape and make the decisions that affect us all.

So, with all due respect to my senior colleague, and any of you other slackers out there, get over yourselves, and go serve on an NSF panel every other year or so.

Allerton Conference, Part I

This week I'll be headed to the 45th Annual Allerton Conference on Communication, Control, and Computing. For those who aren't familiar with it, the Allerton conference is held every year at an out-of-the-way spot nearby the University of Illinois at Urbana-Champaign. (Yes, that's purposely redundant.) The focus is on what CS people think of as EE theory, but as I so often claim, that line is really quite blurry. Lots of information theory and control theory, but there are also sessions on network coding, networking games and algorithms, learning theory, distributed computing, scheduling and queueing, and so on. The organizers are actually very keen on getting CS people to come; offhand I notice that Tim Roughgarden, Vijay Vazirani, Andrew McGregor, and I'm sure several other "CS people" will have papers there. The conference is always extremely well organized, thanks to the fact that it's in the same place every year, and organized by the same people. (I personally have always found the UIUC staff that run the conference extremely helpful. They do an outstanding job.)

One of the interesting things about Allerton is that it's a mixed of invited and submitted papers. The understanding is that if you're invited to give a paper, you're supposed to go and give the talk, not a student. So there are a lot of big-name people giving talks at the conference. Also, invited papers have a lot more leeway. Sometimes, a talk will mostly be a survey, or a discussion of preliminary work on a problem. Some of the best talks I've seen there have been these kinds! Attendance the past few years has been over 300, so it's a nice-sized conference.

I've heard some complaints about Allerton. First, UIUC is out of the way, and the Allerton site is about 20-30 minutes from the main town. If you don't know the place, it's easy to get bored post-conference. Usually the various UIUC hosts have some sort of dinner, and the town is actually a nice small college town. So if you get to know the place and the people, it's not really a problem. (Also, it means the conference is a great place to start a new collaboration, after the talks.) Second, generally there are 6 parallel sessions going on. Many people don't enjoy that. I usually find I'm interested in 2 (coding something and network something) at the same time and have to hop around. Third, I've heard CS people say they don't know which talks they should go listen to -- who are the really good speakers and what are the interesting topics. CS and EE people don't really know each other as well as they should, and there is some cost in getting to know a slightly different area and group of researchers. Fourth, the quality of papers is mixed. Some blame this on the "invited papers", but I think it's just true anywhere, especially for large conferences. Fifth, they don't have a published proceedings in the way that other conferences do. I think that's changing from what I've heard, and these days people just post papers on arxiv or their web page anyway.

The biggest complaint that I would agree with is the conference has grown beyond its location. Some rooms are small and easily get too noisy, making it hard to hear the speaker. The conference has just proven too successful!

I really enjoy the Allerton conference. It's a different set of people than I usually see, but work I'm very interested in. It was at Allerton that I first heard about the coding problem for deletion channels, which I've since worked on quite a lot. I've had multiple collaborations come out of the Allerton conference. I'd really encourage people who don't know about it to take a look.

In the other posts this week, I'll talk about what I'm presenting there, and about interesting things I see at the conference.

Network Coding, Open Problems

I'm spending a couple of days at the DIMACS Tutorial on Algorithms for Next Generation Networks. Tracey Ho and Alex Sprintson and giving a talk on Network Coding, and since in the past I've promised a post on open questions in network coding, I'm interviewing them. I apologize that the questions might be vague; the problem with a new area is that it's still a little unclear what the right open problems are, and we all use different lingo. But here are a few...

1. For 3 source-receiver pairs and unicast, in an undirected network, with arbitrary coding, is there an advantage from coding over routing?(I think the reference paper is Li and Li, Network Coding: The Case of Multiple Unicast Sessions)?
2. General multiple unicast in directed networks: is there an algorithm that, given a network, computes the capacity? For acyclic networks, there's an implicit characterization, but not an explicit characterization; for cyclic networks, there's not even that.
   
3. What is the complexity of finding the optimal (in terms of capacity) non-linear code for various network coding problems? Specific problems include determining the truth/falsehood of the following statements:
1. Given an instance of the general network coding
   problem in a directed graph G and a real number
   r, there is a polynomial-time algorithm which
   computes a solution achieving rate r if one exists,
   and otherwise reports that this is impossible.
   
2. Given an instance of the k-pairs communication
   problem in an undirected graph G and a real number
   r, it is recursively undecidable to determine
   whether the network coding rate is less than r.
4. For multicast networks, what is the minimum number of nodes that need to do encoding to make network encoding work? That is, can we minimize the coding complexity in terms of the number of nodes doing coding (or some other reasonable metric).
   
5. There must be open questions in the recent work by Koetter/Kschischang on coding for errors/erasures in random network coding. For example, they seem to give general (network-oblivious) bounds. Are there ways to improve their bounds by using knowledge of the network topology?
   
6. Is there an algorithm to find the minimum cost subnetwork that guarantees delivery using network coding subject to certain classes of adversarial (or non-adversarial) link failures.
   
7. A good place to look for CS-style open problems is probably also the Adler/Harvey/Jain/Kleinberg/Lehman paper On the Capacity of Information Networks, which has a nice section on open problems at the end.
   

Maybe I'll have more after the talk...

Traveling: International Symposium on Information Theory

I am a big believer that traditional information theory and computer science theory are becoming much more intertwined. Perhaps, someday, the boundaries will be so fuzzy that we won't really distinguish them. Since I don't think that day is here, I'll describe the International Symposium on Information Theory -- a conference, it seems, most CS people don't know about -- where I'm headed this week.

ISIT is the major information theory conference of the year, by which I mean it's huge. I mean, ridiculously huge. Eight parallel sessions huge. I don't know the actual numbers, but I'd guess attendance is in the large hundreds, nearing one thousand, maybe more. I'll ask the IEEE people when I get there.

We don't have a conference like this in CS theory. If we get 300 people to a conference, it's a big deal. We prefer to split things up into smaller, more coherent units. There are pros and cons to both approaches. The obvious benefits of the big conference is that it gets everyone together.

With smaller conferences, CS theory conferences ostensibly have a higher quality bar. As you might expect at such a big conference, with acceptance rates of 50% or higher, the paper quality varies dramatically. You tend to see a lot more preliminary ideas or work that's not as fleshed out as a STOC/FOCS/SODA paper would be -- of course, in ISIT, you only have 5 pages. On the other hand, you'll also get breakthroughs presented here, like Amin Shokrollahi's Raptor Codes.

I am still a bit of an outsider at ISIT, as it is not my regular crowd, although every year I seem to know more faces. So you could view it as simply self-interest that I encourage more CS people to submit and attend. If you're doing anything related to codes (network coding, list decoding, low-density parity-check coding -- all topics many CS theory people are working on), you probably already know about ISIT -- there are lots of session on coding, naturally. But they also have sessions in cryptography, quantum information theory, compression, sequences and complexity, and network information theory. From that list of topics, you might think it's a CS theory conference! But that's the point -- the two areas are increasingly close, and more interaction, including CS people attending ISIT, would help both sides.

I hope to have interesting news to report.

Anti-PC Travel

Over at the new Computational Geometry Discussion Forum, they are discussing program committees, and Ileana Streinu argues that every PC should have a face to face meeting for final decisions. I couldn't disagree more.

Academic life involves a significant amount of necessary travel -- conferences, talks, NSF meetings, research collaborations. Requiring travel for a PC should be avoided, especially these days when any air travel is an unpleasant hassle, and electronic PC tools (like easychair) are becoming reasonably good. My other main objections:

1. Travel wastes PC members' time. For people with families, the cost is particularly severe, as overnight travel specifically takes away from family time.
2. PC travel costs. It either increases the cost of the conference, or PC members have to pay with their own grant money.
3. Extra air travel is ostensibly bad for the environment. Be aware of your carbon footprint!

What are the supposed benefits of face-to-face PC meetings, and how to respond to them?

1. It leads to better decisions. This seems to be a matter of faith with some people, but I have seen no real evidence for it. In my experience, online discussions can be as good as face-to-face discussions. In both cases, there are various types of noise, and decisions will not be perfect, but hopefully nearly so.
2. It saves time, by gathering people all in the same room to make decisions. Given the time required for actual travel, I doubt this is true. Even granting this, it isn't worth the loss in time flexibility. Getting on a plane means missing class, family dinners, etc.
   
3. It leads to better feedback. I do not see how this can be possible. Electronic PC meetings allow recording of comments and discussions, which should make it easier to provide better feedback, in the form of appropriate cuts and pastes, in the reviews to the authors.
4. It provides an opportunity for colleagues to get together. This I can't deny. Face-to-face PC meetings are usually more fun and informative than electronic ones. Does that really make up for the time/cost/annoyance of travel?

So in general, if a face-to-face PC meeting is required, I'll likely be saying no, unless I have some ulterior motive that makes the travel worthwhile.