Monday, July 28, 2008

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

Tuesday, July 22, 2008

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

Monday, July 21, 2008

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

Sunday, July 20, 2008

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?

Monday, July 14, 2008

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

Sunday, July 06, 2008

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.

Friday, July 04, 2008

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

Wednesday, July 02, 2008

Quick Notes from SWAT

1. I'm at SWAT, but don't have much conference news to report; I arrived right around lunch, and went to my room for a post-red-eye nap.

In sort-of-conference news, the hotel is great, Gothenburg is a beautiful city, the organizers seem on top of everything, and I had a very nice dinner with the PC/Steering committee folks. Topics ranged from the difficulty and cost of running a conference, to the "Bell Curve" and IQ, to why people live in Sweden but work in Denmark. And a few technical research-y ideas as well. A nice day. Boy, I hope I don't mess up my talk tomorrow.

2. A place I consult switched to a VoIP phone system requiring me to install phone software on my Mac and gave me a USB headphone set. The upside -- I can call home from Sweden on the wireless! Nice. Yes, I could also use Skype, but calling on a regular phone has its advantages. Yes, I know I'm late to join the 21st century.

3. Following the complexity blog, let me welcome Sorelle to the list of current bloggers. She's a CS theory graduate student who's just started!