Saturday, February 23, 2008

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.

Wednesday, February 20, 2008

Conference Reviewing: Another Rant on Competitive Analysis

Because of an inadequate lack of attention regarding conference deadlines on my part, I find myself currently reading lots of papers while concurrently serving on the SPAA and ICALP Program Committees.

And somehow, this means I'm reading lots of papers with competitive analyses of algorithms. (Both the standard variety, and the more new-fangled but generally similar "price of anarchy" variety.) Looking back on it, I should have simply have told the PC chairs that it might be best to make sure not to assign me any such papers, as I'm not sure it's fair to the authors who get me as a reviewer.

OK, I'm exaggerating. Don't get me wrong; I'm not automatically assigning negative scores to any such paper. Some of these papers I really like. But in general, as I've expressed frequently elsewhere, I'm a skeptic when it comes to competitive analysis. Why exactly should anyone care that you have an algorithm that in the worst case always gets within a factor of 6.5 of the optimal solution possible? Why is that the right way to judge an algorithm? (Never mind the offshoots, like those where you have an algorithm that's competitive if it has twice as much as memory as you allow for the optimal algorithm, and so on...)

In my mind, the problem is that competitive analysis has become such a standard in Theoretical Computer Science that people don't feel the need to bother justifying anywhere in the paper why they should use competitive analysis, when in fact these papers scream for a need for motivation.

Here are some motivations that tend to work for me when reading competitive analysis papers.

1. The resulting problem is just so mathematically interesting that we really have to look at it. (One person I can think of that manages to pull off this motivation with me time and again is Susanne Albers.) Generally, to pull off this motivation, your problem should be simple, clean, and natural; if you start to bog down in details, claiming that you're giving a "more realistic" model of the problem, you've already missed the boat in my mind. (If you really wanted to be realistic, you wouldn't be using competitive analysis...)
2. You are considering the performance of real, existing algorithms. This seems reasonable to me; here's something people actually do (like, say, Shortest Job First scheduling), and you want to gain some insight into its worst-case performance for this notion of worst-case. Many price-of-anarchy results actually correspond to the behavior of reasonable algorithms one might consider in practice, so I admit I often find myself more sympathetic to Price of Anarchy results, which seem more motivated.
3. You are using competitive analysis for an essentially (complexity)-theoretical result.
4. You are using competitive analysis to gain significant insight into the problem (and algorithms for the problem) that could be useful in understanding real performance or designing real algorithms. I think most papers implicitly claim that their paper fits into this last category, just because it obviously doesn't fit into the other three, but usually this isn't explicitly discussed. I think this motivation works best when the problem is inherently very hard.

I'm sure there are other reasonable motivations. But overall I would call for more restraint from the community; not everything should be subjected to competitive analysis, just because it can.

Sunday, February 17, 2008

Some News from Harvard

A few interesting pieces of news from Harvard.

First, Harvard is setting up a scheme to avoid restrictive access policies of some journals. Essentially, as I imperfectly understand it, Harvard is obtaining from the faculty a non-exclusive right to disseminate articles written by the faculty. The intention is that a Harvard faculty member should be able to say to any journal that insists on having an exclusive copyright to an article, "That's fine, but I work at Harvard, and as such Harvard has a non-exclusive right to my work, which will be placed in an open repository." Stuart Shieber, a Harvard computer science professor and a strong proponent of open access, was behind this faculty legislation. Perhaps all the universities can get together and give a message to the journals that they are the ones that actually pay the faculty, and they will work against journals where the business model depends on restricting access to the research to only those who pay a monopoly-based fee.

Second, the Dean for the School of Engineering and Applied Sciences at Harvard, Dean Venky, is stepping down. Venky and I began about the same time at Harvard, and he's done a lot for improving the visibility and status of computer science and engineering at Harvard. I hope we can find a new Dean that can continue the push to build up these areas at Harvard.

On Valiant

I was avoiding posting on Les Valiant's EATCS award and the obvious question about the somewhat odd fact that he hasn't yet been given his Turing Award yet because of the amazingly obvious bias I would have (such as being on the same faculty with him). But now that it's shown up on the complexity blog, I feel unrestricted.

From my standpoint, Les is an "old-school" scientist. He spends a long time thinking very deeply about difficult problems, trying to come up with results or frameworks that will fundamentally change how we think about something. And as the list of his results show (see the complexity blog post and comments; whatever you think Les has done, he's done even more than that), he's been amazingly successful at it; he's had several once-in-a-lifetime results. As part of his style, he doesn't care about his paper count or h-index. This type of science is incredibly risky, and not for everyone. But it's a remarkable example of what's possible.

Tuesday, February 12, 2008

Class Demographics

This year, my undergraduate algorithms and data structures class is about 25% women. This is significantly more than average (enough that I noticed). Based on previous experience (and initial impressions from the first few lectures), these women will be very strong candidates for graduate school should they choose to apply when they graduate (one or two years from now). (I could simply be suffering mental bias from the various studies I've read, but my recollection from prior years is that when there's a larger cohort of women in the class, they generally perform better overall. I leave others to postulate on causes and effects, or to argue whether my data point is unrepresentative.)

Saturday, February 09, 2008

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?

Thursday, February 07, 2008

Class Reviews

I just received the class reviews for my Randomized Algorithms class. Historically, I have found my reviews are bimodal. Some students describe me as their favorite professor (and end up taking all my classes). Some students describe me in fairly unflattering terms. This year was pretty much the same.

The most signal from the noise was worth hearing, although pretty much stuff I already knew. First, students would like more of my time. I apologize for being busy, I suppose. Second, it would have much better to have had a TA. I agree (you think I enjoyed grading problem sets???). Sadly, my first choice TA was (rightly) busy working on his thesis, and there wasn't really another appropriate graduate (or undergraduate) student. But going without a TA is not something I'll try again.

A lot of the rest of the comments are lost in the jumble that comes from teaching to a class that serves a wide audience, not just theory folks. Some thought it was too fast, some too slow. Some liked that we pretty much followed my textbook, some thought I should let people read the textbook on their own and cover other stuff. Most found the problem sets a "challenge", which I think is just fine.

Class reviews never answer the question I really want answered. Five years out, was my class worthwhile? Has it had any impact on your research/job/worldview/life? Or even if you don't see an impact, do you remember it as a worthwhile learning experience? I don't care if you come out of the class thinking I'm some sort of sadistic homework machine (but really, I'm not...), if a few years down the road you find it was all worthwhile.

So ex-students -- not just MY ex-students, but all ex-students -- if you have a class you particularly liked several years back, a class that sticks in your mind or a class where the material has proven really useful to you later on, please send an e-mail to that professor and let them know. Anonymously is fine. That's the kind of feedback that means a lot to teachers. And you can even do it if you had a course you particularly disliked -- at least I wouldn't mind hearing from students who years down the line still think that I did a terrible job if they have constructive contributions to offer.

Wednesday, February 06, 2008

On Comments

I've noticed a phenomenon surprising to me on this blog: comments trickle in regularly on older posts. Whether that's from new readers discovering the blog and going back over old posts or regular readers who take a while to think about what they want to say, I thank you, and welcome your comments and questions always. (OK, I don't always have time to answer all the questions...) But it's interesting to me that the active lifetime of a post can be substantially more than a week.

More generally, I would like to figure out how to get more people commenting on the blog. I try to discuss issues here where there can be a variety of opinions and room for tangents, and I think the most interesting part of the blog is in the discussions. I'm genuinely surprised when I go to conferences and people tell me they read the blog, since in my mind the corresponding comment-level seems sparse.

So feel free to comment on what I can do to make the blog more comment-friendly.

Tuesday, February 05, 2008

More on the Shopping Period

As I mentioned two posts ago, Harvard has an unusual tradition of a "shopping period" -- you don't preregister for a class, but you choose classes after the first week, after you've had a chance to go to a lecture or two and see how you like it.

As a student, I loved it. What better way to get an idea if you'll like a class than to go, hear the professor, check out the syllabus, see who else is thinking of taking the class, etc. It makes choosing classes much more flexible. Instead of switching out of classes you've already chosen without seeing, you choose later. Part of that benefit might just be psychological -- most schools allow you to change courses in the first few weeks fairly easily -- but there is a marked difference between changing your classes and choosing your classes, especially if a student has to fill out forms or get signatures to change a class. The openness of the first week is a real benefit to students. I can understand why something like shopping period just might not be feasible for some very large schools, but I think it's a shame more schools don't do it.

Several years ago, there was a movement by the administration to introduce preregistration and get rid of shopping period. I was on the Committee for Undergraduate Education and the Faculty Council, and when the idea was first brought up I spoke against it, only to find that the issue didn't seem up for discussion; it apparently had been "decided" higher up. (It's things like this that helped make the Presidency of Larry Summers so unpopular, as opposed to some of the supposed reasons popularized in the press.) I was surprised that so many faculty on these advisory committees seemed willing to go along with the idea. It was massively unpopular among Computer Science faculty; we like students being able to choose their courses.

Overall, naturally, students didn't seem to like the idea. The administration's main argument seemed to be that it would allow more accurate predictions of class sizes in advance, so Teaching Assistants (and, in some classes, classrooms) could be assigned more readily and efficiently. (Here's an old Crimson opinion giving both sides of the issue.) This was around a time period where there were murmurs of graduate student unionization, and that might have been influencing the administration's mindset. Of course, nobody in the administration had an answer when I asked what prediction mechanisms they were using now, and if there was any evidence that preregistration would help predictions any. (I wasn't the only one asking this question. This was another reason the CS faculty in particular were against the idea; they saw no reason for it. It's in interesting problem to design an enrollment predictor; one semester, Stuart Shieber ended up running a projects class to find solutions for the problem.)

A funny thing happened, though. The change had to be approved by the faculty, and while I seemed to be a lonely voice with objections in these committee meetings, apparently a lot of faculty didn't actually like the idea. Instead of it being a quick and simple vote like the administration seemed to expect, the faculty meeting was a disaster. Eleven faculty spoke on the issue; ten spoke against it (including, I'm happy to say, me). Quietly, pre-registration was dropped as an issue, and shopping period continues.

Monday, February 04, 2008

Microsoft Cambridge Lab II

It's officially hit the wires, Jennifer Chayes and Christian Borgs will be heading up a new Microsoft lab in Cambridge II -- that is, here by Harvard and MIT. The proposed theme is interesting (and, happily, very appealing to me) -- algorithms with an emphasis on social networks and algorithmic game theory.

It opens this summer. I can't wait to see how it plays out.

Saturday, February 02, 2008

Shopping Period Lecture

One of the great Harvard "traditions" that I enjoyed as a student is the "shopping period". Students don't pre-register for classes; they spend the first week "shopping" whatever classes they like, and then choose what ones they want to take. (I'll talk more about the "politics" of shopping -- the pros and cons -- next time.)

Because of this, rather than dive right into material the first class for my Algorithms and Data Structures class, besides going over the syllabus and requirements, I do something that at least I consider fun. We talk about how to get fair bits from a biased coin. The class starts with the classic brain-teaser: suppose you have a coin that may be biased. How can we flip that coin to decide something fairly, like who should pay for lunch?

[The simple solution to this question, unless I'm mistaken, is commonly attributed to von Neumann.]

Starting from there, I try and take the class through a series of questions, leading up to how to efficiently extract lots of random bits from a sequence of biased flips. The method I base the lecture on is due to Yuval Peres [(see "Iterating von Neumann's Procedure for Extracting Random Bits," Annals of Statistics, March 1992)], and I learned about it at some point in graduate school at Berkeley. I try to run this lecture in a very back-and-forth manner, asking questions of the students and trying to get them to answer. (I also do this a bunch during the semester, with varying degrees of success...) Here's a version of my notes, with the various questions.

For the students who decide not to take the course, I figure at the very least they've learned something interesting that they can take with them. Also, it's conceivably the only time students will hear the word "entropy" in a computer science class, so I think it's worthwhile for that alone. Somehow, this problem fascinates people. Way back when I had more energy, I wrote a Dr. Dobb's article on it to show it to a wider audience, and there's been lots of related research on the problem. In some sense, this problem is the pre-history of all the randomness extraction work that has come since.

Thursday, January 31, 2008

Algorithms for Newbies: Static or Dynamic?

A talk I just went too (by Lynn Stein) raised the following question for me.

While I have some strange ideas about how an algorithms class should be taught (like students should do some programming in an algorithms class), in most ways my algorithms class is quite traditional. Roughly, my class looks quite similar in the path it takes to Algorithm Design by Kleinberg/Tardos (or the corresponding subsections of the standard Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein). And specifically, I teach primarily what we'd call "static" algorithms; there's an input, a desired output, and the algorithm is the recipe.

These days, many of us do research in and arguably most commercial products use "dynamic" algorithms; that is, they're processes that are always on, reacting to the environment around them. (Your cell phone, for example, might be considered a dynamic algorithm device; so would a robot vehicle. If you like, you can think of "dynamic algorithms" as roughly being closely tied to "distributed systems".) My course is not geared to teach or have student explore dynamic algorithms, although they get brief mention. Lynn seemed to be suggesting that dynamic algorithms and programs should be taught before static algorithms and programs. It is, after all, the paradigm students are most familiar with, and arguably more interesting to them.

This doesn't sit right with me. In my mind, it's partly a "walk before you can run" issue -- you could teach a lot of calculus without teaching trig, but it doesn't seem the right way to go. Although that's not really quite the right analogy; I can see that the issues in dynamic algorithms/distributed systems -- like communication, and responding to asynchronous incoming signals -- are often quite different than for static algorithms, so much so that in many case you don't have to know your standard static algorithms to write a dynamic one. I think it's more that I think that to do anything that I would consider technically interesting you need to know static algorithms first. That is, sure you can probably teach people to write an interactive Internet chat program pretty easily, and they'd learn a lot by doing it, but that's like the task 20 years ago of writing a checkbook program, just harder because of issues raised by the interactivity. To do really interesting things with dynamic algorithms, my bias is you need good static algorithms behind it. Like Google mail's search features, or Amazon's recommendation feature, or other stuff. (Or at least, in many cases, you should understand the static version of an algorithm before trying to understand the dynamic version of it.)

So now I'm wondering if I'm just old-fashioned. What do you all think?

Tuesday, January 29, 2008

More SODA Stuff: Congratulations to Susanne Albers

Another fun SODA activity: getting to (belatedly) congratulate Susanne Albers on her Leibniz Prize in person. I had the great pleasure of working with Susanne early in our careers, and I'm thrilled to see her get this kind of recognition, which she greatly deserves. (A paper of hers I remember greatly enjoying was On Randomized Online Scheduling, if you're looking for a starting point to check out her work.) And 2.5 million euros is real money, particularly at the current exchange rate!

After my queries, Susanne politely explained to me that the money could not actually be used to buy a house, but was for research. I suggested that now was a very good time to ask for a raise. More banter followed. Certainly, one of the pleasures of conferences is catching up with colleagues in distant places. Congratulations Susanne!

Sunday, January 27, 2008

The CRA blog on NSF Funding

If you aren't regularly reading the Computing Research Policy blog at the CRA, I recommend stopping by once a month or so. This month: find out about the latest NSF funding disaster (or "how the NSF and science in general got shafted in the budget process yet again") , including whether CDI will actually get funded (after we suckers researchers sent in 1300 proposals for about 30 grants...)

Friday, January 25, 2008

Harvard's Financial Aid

Bill Gasarch asked me to comment further on Harvard's new financial aid policy, which I briefly mentioned here, a post which strangely has gotten a few comments in the last 24 hours. (Of course, some crazy people have the wacky idea Harvard should be free.) One of the comments points to a recent op-ed piece in the New York Times; another commenter calls the piece illogical, which I'd have to agree with.) I'll offer my opinion, which has been colored by discussions with Harry Lewis. (By the way, have you bought his book yet?)

First and foremost, I'm glad Harvard did it.

One complaint is that Harvard only did it to stave off potential future legislation requiring it to spend more of its endowment. I just don't think this is true. Harvard has been raising its financial aid already quite substantially the last few years. There are plenty of other motivations and pressures to do so outside some sort of potential future legislation. In particular, if there are any political motivations, I'd say a more likely one is that the new President of Harvard and Dean of FAS did it to show some leadership and put a positive spin on their new administration out in the news. But I don't even think that's such a big reason. It's the direction Harvard's been moving for some time.

Another complaint is that this will put pressure on other schools who can't afford to do the same thing, particularly public schools, who will lose some talented students. I don't see this as a huge problem. Harvard only takes about 1700 students a year. Even if the whole Ivy League tagged along (like Yale has), that leaves plenty of talented students -- including the ones who would have gotten into Harvard but now didn't because the financial aid allowed a similarly or higher qualified student with fewer financial means to attend. When Harvard expands its entering class by a factor of 2, then people can complain what a terrible thing Harvard is doing, stealing good students away from other institutions. (Their argument will still be weak and misguided, though.)

I like how the two major complaints are so contradictory in nature. The first says Harvard isn't doing enough with it's big endowment; the other says Harvard is doing too much.

Me, I'm thrilled. Harvard did something good: it made attending Harvard more affordable. In doing so, it showed leadership, and has got people talking about the cost of college in places like the Opinion page of the New York Times. I hope it will lead to further positive changes, and improve the affordability college more generally.

Thursday, January 24, 2008

The Job Search, Another Perspective

I am chairing the search committee for Harvard this year, motivating me to comment on the view from the other side of the search process. Everything here should be taken as general commentary, my own opinion, not the opinion of my employer or this search committee, and not necessarily specific to our search, which of course I can't discuss in any detail. (The following comments are not theory-specific, though I use theory-examples.)

A general search begins with getting several hundred applications for a small number of interviews and an even smaller number of eventual offers. Candidate quality is quite high, to the point where it's very difficult to whittle the folders down to a number that can be reasonably considered for interviews. [I'm personally doubtful that there will be enough academic/research lab jobs available this year (in, say, North American academic institutions) for all the highly qualified candidates. All the good people will get a job, I'm sure -- perhaps just not in academia, or in research labs. We'll lose people to non-research industry. That's not necessarily a bad thing, but I'm sure there are plenty of people who would like to stay in research that won't be able to. Of course, even if you get an academic job, it's not clear these days there's enough research funding to go around for everyone, anyway...]

Candidates need to find a way to stand out. More precisely, their research record needs to stand out. Somehow, unfortunately, it's not even enough to have a number of papers in top-tier conferences. In theory, for example, there's a number of people with multiple FOCS/STOC/SODA papers. Let's hypothetically say there's a dozen candidates with 3 or more papers in top-tier conferences in an area. What will make you stand out as one of the top two or three that gets an interview?

Letter-writers confirming the quality of your research (and your contributions on multi-author papers) are one obvious answer, and this partially explains the often observed hiring bias in favor of students from top-tier institutions; they have top-tier letter-writers. It is, generally, helpful to come from a top-tier institution, but it's less clear that it matters which particular one. Research quantity is another way to stand out. Those rare extreme cases of people who manage to publish 20 or so papers in top conferences do get noticed, certainly.

Quality, however, matters much more than quantity. Are you working on exciting problems, that can have a significant impact in some way? Are you following the crowd, or getting ahead of it? In essence, the question is "What is candidate X famous for?" If there's a good answer to that question when you replace "candidate X" with your name, you're much more likely to get an interview. And the statement "Candidate X is famous for writing a lot of papers" isn't really sufficient in itself.

Finally, I think there are further intangibles that contribute to this notion of reputation that need to be thought about earlier on in graduate school that impact the hiring process. Giving good conference talks gets you and your work more notice, increasing the fame factor. Working with many people, including people from outside your home institution, increases the visibility of your work (and improves your collection of letters).

In the end, of course, all this advice seems obvious. Then again, being on the search committee and writing this up clarified it my mind, and will make me reflect on my own recent work practices.

Wednesday, January 23, 2008

The Job Search, One Perspective

Of course the most interesting part of the SODA conference (and generally all conferences) is the conversations one has out in the halls. At some point in talking to one of the many people job-hunting this year, my own employment history arose, and at the risk of self-indulgence I thought it might be instructional to repeat here.

When I was finishing graduate school, the job market wasn't great. Most people went into postdocs. Your Jon Kleinbergs and David Kargers got jobs, of course, but most top 36 schools weren't hiring theorists out of graduate school. I felt pretty fortunate; I had interned at Digital Systems Research Center (SRC -- which, sadly, is now before-many-people's time...), and it seemed reasonably likely I might be offered a job. I also applied for several postdocs just in case, and applied to a small number of universities. I avoided a wide search, figuring my chances were small, and that I'd rather do a postdoc than take a job somewhere I didn't really want to go.

I got a small number of faculty job interviews -- including an interview at Harvard. But, at the end of the day, no academic offers. I did, happily, get a job at SRC. I think from the perspective of many graduate students, this would be seen as a failure -- no faculty job! (In telling the story at SODA, the look in the student's eyes seemed to suggest that interpretation.) In hindsight, of course, it's easy to see that this was far and away the best possible thing for me. SRC was a great place to be, full of innovative people and a strong ethic of theory/systems collaboration, and I received the benefits of mentoring from many great researchers (particularly Andrei Broder), as well as time to develop my research abilities and profile.

I decided to throw my hat in the ring again two years later. Since I liked SRC, I again only applied a small number of places that I might conceivably leave SRC for. I got 3 interviews. And just one job offer, at Harvard, which had rejected me last time around.

I suppose in this rambling anecdote I'm hoping there are some messages job-seekers current and future might take away. Patience really is a virtue; you needn't get to where you're going immediately. (It seems many CS theory folks have had long, winding, and quite pleasant careers.) For many, it might be beneficial to have some time and experience before facing the pressures of the tenure clock. You should never take it personally if you don't get an interview or a job offer. Don't be afraid to fail. Summer internships are a very good thing. Research labs are a very good thing.

I'm sure many job-seekers, having gone from undergrad right to grad school, feel the pressure to get to right to the next step, a tenure-track position. It might not work out that way. But there are many paths to a happy career; I hope you don't get so tied up in the process that you stop enjoying what you're doing.

Tuesday, January 22, 2008

More From SODA, Andrei Broder's talk

Andrei Broder gave an interesting invited talk on the new area of "computational advertising". As Andrei was my mentor for several years, and historically speaking, I am always thrilled by his work and his insights, consider this a gushingly positive review.

The talk started with a wonderfully complimentary introduction by Allan Borodin, who described accurately how Andrei was one of the initial leaders in the area of Web search algorithms, and his early success is a large part of the reason that so many people from our area have become involved in the field.

Andrei described computational advertising is a new scientific sub-discipline, at the intersection of search, information retrieval, machine learning, statistical modeling, etc. The main problem: find the best match between a given user in a given context and a suitable advertisement.

Andrei started with a brief introduction to advertising (brand marketing vs. direct-marketing, the $$$ behind advertising), and then focused on issues related to sponsored search (keyword driven ads) and content-match (context driven ads, e.g. driven by a page content), although he mentioned the field is much bigger than that (auctions, ad exchanges, privacy/legal issues, etc.). He emphasized the point that ads are "information". Irrelevant ads annoy; relevant ads inform and generate interest. Perhaps the most challenging fundamental question in sponsored search is how to find the right ad. Current practice allows broad matches -- if you want to advertise a Seattle hotel, you can broad match to Seattle or Seattle hotels, but this creates lots of false positives and false negatives. (You match too many things you don't want, and not all that you do. As another example, see my post on what pops up when you do searches related to theory.) What you really want is to match queries related to Seattle as a travel destination. How can that be done? How can you price query matches of these types, since it's not based on bidding on specific keywords? Notice that a lot of this now depends on semantic vs. syntactic matching -- understanding the intent. Similar questions arise in content match advertising, where there is the additional trouble of having a publisher of the page content involved. A further aspect is understanding the context of the user, potentially based on user profiles or recent past history.

One way of understanding context, naturally, is to use a search engine. To classify a keyword phrase, one could look at the search engine results, and re-define or interpret the keyword according to these results (say by giving it a category, to match a collection of ads). This can be made fast by classifying pages offline, and then use pages returning from the search query to "vote" on a category for the query (rather than text-analyzing returned pages on the fly). Even a weak classifier of pages does well if you have a reasonable voting scheme! Similar ideas can be used in content ads, using a mix of category and semantic information to find ads to go with a page. Andrei also raised the issue of caching ads; when are queries "close enough" that you can use a cached from a query-ad pair that may live in a cache?

I left the talk with the feeling that there were a lot of challenging "algorithm engineering" problems here. It's often hard to prove things in real-world settings, but one often needs real algorithmic insight to design solid, well-founded approaches to these real-world problems. This is why Google and Yahoo and MSN are hiring a lot of theoretically minded people. For such companies, there is always the aspect that one may have to give up some intellectual purity when working in these areas. You can't prove everything, and you need to make things that work. But this is a tradeoff. Not just a tradeoff in terms of money (though that's certainly there), but in terms of having a large base of users who actually use and gain from your algorithmic ideas. It's a tradeoff typical when working at theory/practice boundary, but here there's a pretty clear economic/users motivation that's really pushing this area forward. I think the talk did an excellent job of introducing the basic problems and motivation to a general (theory) audience.

Monday, January 21, 2008

Some Thoughts from SODA

There are many reports from SODA at the various theory blogs, but here's a quick report:

Persi Diaconis gave a great talk on interesting connections among carrying, shuffling, and Young tableaux. The starting point: consider adding m n-digit numbers, where the numbers are uniform base b. Then the possible carry values are between 0 and m - 1. For large n, what's the fraction of time the carry value is 0, 1, 2,... As the carries process is a Markov chain, this can be determined. He then connected this to theory of shuffles. Here's a nice model for a shuffle; each "card" corresponds to a point chosen uniformly on [0,1]. An a-shuffle maps x-> ax mod 1. The resulting re-ordering is a shuffling of the cards, which leads the way to analysis. From there he went on to tableaux.

Rather than try to summarize the talk, I'll point to his major references:

John Holt, Am Math Monthly: Carries, Combinatorics and an Amazing Matrix
Persi Diaconis, web page, papers from 2003: Mathematical developments from the analysis of riffle shuffles
R. Stanley: Volume II, enumerative combinatorics, chapter 7

He left open the problem of trying to develop a clean, pretty correspondence between the carrying process and shuffles.

Muthu conversed in the morning about MapReduce; see his new blog entry. In particular, the perspective and counterperspective on MapReduce in this post from the Database Column is quite entertaining.

I enjoyed the talk for (and want to understand the paper for) Improved Algorithmic Versions of the Lovasz Local Lemma by Aravind Srinivasan (who didn't give the talk, but it was still well-given). The Lovasz local lemma is quite beautiful, although I don't think I've ever used it in a paper. I'm inspired to try to find a good use for it.

Friday, January 18, 2008

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.

Wednesday, January 16, 2008

Meetings with Graduate Students

I think one of the signs a graduate student is on his or her way to graduating is when they start taking control of our meetings. With younger graduate students, I've found I have to set the agenda -- asking questions, pulling out information from them, and telling them things they need to do. Some time ago, I noticed that Adam was coming into our meetings with a written agenda. He asks me questions, gets information from me, and tells me what I need to do. And then, on a good day, we can collaborate on research.

I'm not saying that graduate students can walk in, day one, and take control like that. Indeed, most probably can't and shouldn't. But as a graduate student, the sooner you can take charge of your education and set your own agenda -- so your advisor is a resource, rather than your manager -- the better off you'll probably be.

Tuesday, January 15, 2008

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.

Sunday, January 13, 2008

NSF-related stuff

Although it might seem like it, I haven't really been on vacation -- just a vacation from blogging. One thing I was doing was sending in an NSF preliminary proposal for CDI (Cyber-Enabled Discovery and Innovation -- an unwieldy name I never remember without looking up), with that inspiring January 8 deadline. I was also doing minimal work on an Expeditions pre-proposal, thanks to enterprising colleagues who will probably seek payback if we get to submit a full proposal.

Does anyone have an opinion on this whole letters of intent/pre-proposal system for these new grants? Letters of intent I understand -- it's good to know how many people intend to apply for a new grant. But pre-proposals? Does this minimize the work for anyone? Sure, a 6 page pre-proposal is somewhat easier than a full proposal, but there's still a high overhead in just getting something off the ground (and getting it in the Fastlane system). And the tradeoff is now you may have to do a preliminary and full proposal, and there have to be 2 panels (1 for pre-proposals). I'd be happy if I thought someone from NSF had done the math and found that this approach would really save time and effort on our (the researcher) side and the NSF side, but I somehow think this was inspired some bureaucratic incentive I wouldn't want to imagine. I'd be happy to be proven wrong, if anyone has inside information.

So while at this point I'm sick of proposals, and would love to spend time actually doing research instead of writing to the NSF about research I'll happily do if they fund me, I see a slew of proposal deadlines coming up that I might end up applying to, and are certainly worth mentioning to the blog audience. Rather that point to individual calls, here's the link to the CISE list:

1. Theoretical Foundations. March 19 deadline. Looks standard. SING is still there. Nice to see that this time PIs can apply on two grants -- last time I applied, it was just one.
2. CyberTrust. March 24 deadline. I've never applied to this, but I hear many crypto/complexity people have had success.
3. NeTS. March 25 deadline. That's networking, for you theory folk. It looked like they've really revamped this call, completely changing all of the subareas. I'd say the subareas look more theory-friendly, with areas like Network Ecosystems and Exploratory Networking. But theory-friendliness seems to be at the whim of the panel, in my experience. (Sometimes that's good, sometimes that's bad.)
4. Assembling the Tree of Life. March 14 deadline. Not my kind of stuff, but I do know some theorists have received funding for algorithmic work on Tree of Life problems.
5. Human and Social Dynamics. February 19 deadline. Still plenty of time.

Sigh. So many calls, thankfully, not enough time to do them all. I wonder what's with the tightly grouped deadlines.

Monday, December 31, 2007

Theory and Fashion

I often end up using the Google search bar as my navigator, so I've been surprised of late when typing things like "theory cs aggregator" in to see ads with taglines like

Theory at Bloomingdale's
Theory on Sale
Theory Fashions

I didn't know CS theory was popular in the mainstream!

Theory is apparently a New York clothing design firm, and their wares are in most of the major chains (Saks, Neiman Marcus, Nordstrom's, etc.) So when you look up anything related to theory, and it's vague enough that Google isn't sure what sort of ad to throw at you, you end with clothing ads. I believe their website is www.theory.com, an address I suppose I should have purchased years ago.

Yes, www.cstheory.com is taken. (Smart thinking, Kevin...)

Wednesday, December 26, 2007

K'Nex Computing

Building an adder out of K'Nex.

I never know what to make of these sorts of stories. While I admire the enthusiasm, is this really what gets these students (and others) excited about computing? Somehow, it seems like the equivalent of writing your own iambic pentameter poetry in Latin. The result should be worthwhile for a small, small number of people.

Yet here I am linking to it.

Thursday, December 20, 2007

Women in Theory of Computer Science Meeting

Although it's been well-covered in other blogs, I would be remiss not to mention the workshop for women in theory of computer science being organized at Princeton.

I'm always torn when I hear about such things. I think it's a very good and important idea, but at the same time, I look forward to the day when such workshops won't be necessary (and wonder why we're not there yet).

I do think that peer support is key to getting women into computer science, and having them stay. Some years ago at Harvard we were fortunate to have a group of four very mathematically talented undergraduate women, all of whom apparently had at least met each other in high school, come through the computer science ranks. It was clear that the "group dynamic" of being able to work together and talk with each other was very helpful to them. Three of the four went to graduate school in computer science; two are/have finished (in theory), one switched over to economics. While I have seen many strong women undergraduates come through Harvard, I haven't seen a group quite like this one, and I wish I saw more.

Of course, it also helps to have successful role models, so I suppose now is an apropos time to belatedly congratulate Susanne Albers for winning the Leibniz Prize. I had the great fortune to start working with Susanne while I was a graduate student at Berkeley and she was a postdoc at ICSI. It was a great experience for me, as at the time, I was still figuring out how this whole research thing worked; I learned a lot working with her. I'm thrilled she's getting this outstanding prize and the corresponding recognition for her body of work.

Monday, December 17, 2007

A New Book by Sean Meyn

I've found what to ask for my Cambridge University Press rep for my holiday present -- a new book Control Techniques for Complex Networks by Sean Meyn.

Other new bookshelf suggestions are welcome...

Wednesday, December 12, 2007

Hash Collisions -- Economist Article

The economist has a nice story about recent work on creating documents that yield MD5 collisions.

Monday, December 10, 2007

Harvard Improves Financial Aid

Harvard's is again improving its financial aid policy, as described here and here.

It's not as wacky or ludicrous an idea as not charging anyone tuition, but I'm still glad to hear it. (Wait, this doesn't cut my salary, does it...)

Friday, December 07, 2007

Preparing Students for Jobs

In a recent "discussion" on another blog, I repeatedly heard the refrain that we ivory-tower pie-in-the-sky university computer science professor types just aren't preparing students suitably for "real-world" employment. Personally, I think that's just BS. However, I realize I may have a fairly biased viewpoint. I teach at Harvard, and, if I may say so, our students are generally quite good and do well in the job market. Having spent some time in industry, and, if I may so so, being perhaps more interested than the average theorist about practical issues, I attempt to add "real-world" aspects to my classes, like programming assignments in my undergraduate theory course.

Now occasionally I catch students who admit to reading this blog. I mean all students, from whatever school, undergraduates and graduate students, not just students from my classes or Harvard students. I hope some of you are reading now. Because I'd like to ask you to enlighten me. (That means, for instance, I'll keep quiet on the comments.) Please tell me, in your experience, did your education prepare you for your life after in the real world. (For current students, you can comment on how you feel your education is preparing you.)

While I'd expect you to comment anonymously, I'd ask that you provide salient information where possible. (Harvard student or not, current undergraduate or long-time real-world person, CS or EE or other major, etc.) I'd also greatly enjoy hearing specific comments and criticism regarding my own classes, from any ex-students out there.

And in advance of some annoying anonymous commenter who might feel the need to say how out of touch I must be that I need to find out how students are doing by asking on my blog, please rest assured I have other sources of information (both personal and data-driven) on the subject, but this is, hopefully, an interesting opportunity for me and others to gain more insight.

Thursday, December 06, 2007

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.

Wednesday, December 05, 2007

SIAM is Spamming Me

Many of us received a note from SIAM today, starting with:

Dear Speaker:

We are so pleased that you are going to be a part of the ACM-SIAM Symposium on Discrete Algorithms (SODA08).

Please be advised SIAM has not yet received your conference registration. Although you may register on-site, SIAM requests you register in advance to confirm presentation of your paper.

I had to search my e-mail, to confirm my memory that I had in fact registered. I sent a note back to the sender explaining I had an e-mail confirmation, and got back this response.

Dear Michael Mitzenmacher,

Please note that this is a mass mailing. It clearly states and the end of the registration reminder

“If you have already registered please disregard this message”.



Indeed it does. But why then send a mass mailing saying clearly at the beginning of the message that they haven't gotten a registration, instead of just sending a reminder that speakers need to register? What makes this SIAM conference person (whose name I'm politely removing) think this is OK? It's not to me. I've sent a complaint, and I plan to complain further to SIAM staff at the conference.

Tuesday, December 04, 2007

Discussion over at the Complexity Blog...

For those who miss my regularly scheduled program, I'm busy inciting arguments over at the Computational Complexity blog on quiz-style interview....

The regularly scheduled program will return shortly.

Wednesday, November 28, 2007

NSF FIND Working Meeting

I'm writing this while stuck at attending an NSF FIND (Future Internet Design) working meeting (Nov 27-28). Part of the FIND program is that there are 3 meetings per year where all the FIND PIs are supposed to get together, to talk about the new network that is the goal of the FIND program. This is my first meeting; I missed the last one. It seems to me that this idea of having PI meetings related to grant proposals is an NSF experiment worth examining, and there are some discussions going on here that may be of broader interest, so I thought I'd report. (If this reads as stream of consciousness, I'm generally typing as things go on.)

One positive for me is the chance to catch up with various networking people who I don't see so regularly. The socializing aspect -- just talking to people, finding out what they're working on, making sure they know Harvard is hiring, all this is good. (Jennifer Rexford and I chatted during a break, and when I sat down after the break, she had already sent me a paper to look at. Which I need to go ask her some questions about... I also finally caught up on some overdue researchy discussion with Dev Shah of MIT; yes, I have to go to DC to meet up with someone from MIT...) In this sense, it's like going to a networking conference, and obviously interacting with peers is one of the pleasures of a conference.

The invited presentations aren't doing much for me, however. They're not highly technical talks -- more high-level talks, connecting network research to network users. (We're hearing two talks right now about issues in the practice of emergency networks in disasters.) It's not that the talks are bad, but it's a bit hard to see their purpose. This is a room full of networking people -- they all have well-developed individual research agendas and know what they think the problems are. I don't think the talks are adding much new. (Let's just say I'm not the only one tapping away at the keyboard when I should be listening to the talk. So again, it's just like a conference.)

Besides invited presentations, there are break-out sessions. I'm sitting in on the "network management" breakout session, which far and away seems the largest. About 25-30 people or so in here. It's actually kind of like a conference panel, only a bit more chaotic with so many people. While the discussion is high-level, and I'm not sure we're headed anyplace specific, it's actually a pretty interesting discussion that highlights the scope of the problems of network management. (So many requirements, so many heterogeneous user classes, so many ill-defined goals, so many ill-defined or at least hard to measure quantities, etc.) Interestingly, the group as a whole seems quite convinced of the importance of what I call theory -- modeling, control, algorithms. (The pro-theory comments seemed to begin from Jennifer Rexford and Anja Feldmann, two incredibly pro-theory and powerful network researchers.) This gives me a good excuse to chime in and further emphasize the importance of theory to network management, which I manage to do repeatedly.

Ellen Zegura is giving a talk about GENI and the GENI Science Council. The GENI Science Council is supposed to come up with a "research plan" for GENI, an experimental facility/infrastructure for the development of the next generation Internet. (Network people rightfully complain it's hard to do experimental research on the current Internet at a large scale, so the plan is to design a research infrastructure for these sorts of problems.) There's a notable shortage of theorists on the council, but they seem to have noticed this and added Joan Feigenbaum and Michael Kearns recently. (From my perspective, if you're going to design a whole new network infrastructure, it seems to me you'd want some theorists to help make sure it's done right.) They're still putting together the research agenda that goes along with the planned facility, and they're still looking for input. Essentially, it seems like they're looking for research examples and research experiments that would utilize or benefit from a GENI-scale system, so that they can explain clearly why building a GENI-scale system is a good idea. So if you have ideas for experiments that you'd like to do on a network-wide scale, you might start looking at what GENI's up to. Overall, GENI seems like such a huge project, and it's still a bit amorphous at this point, so that people are a bit confused. Or maybe that's just me. (I did have to get up at 4 am to catch the early plane down here.)

I talked with Ellen later, and got clarification of the GENI state. I had thought this was well on its way to becoming a possibly multi-hundred-million dollar new NSF project, but apparently it's much less further along than I had thought. If GENI is going to happen, it apparently needs to regain some momentum. And GENI seems a key component of the FIND program; it's hard to develop next-generation network architectures if you don't have a network to try them out on.

Before dinner they have a poster session. It's well done for a poster session -- they have food and a cash bar, and food and drink always seem to be requirements for a poster session where people actually stay and look around. There's a nice mix of work; my favorite is an idea multiple groups seem to be working on that there shouldn't be just one network architecture, but multiple network architectures running over the same network substrate. My interpretation is that you have routers/other infrastructure that can run multiple architectures efficiently in parallel, so running side by side you might have our standard Internet with another network with much stronger (or weaker!) quality of service guarantees, or another network where connections are based on virtual circuits, and so on. This makes sense if you believe that a one-size-fits-all Internet is no longer the best idea.

Day 2 is mostly having the breakout session coalesce their ideas into short presentations. Pablo Rodriguez, of fame for example for his work on Avalanche/network coding at Microsoft, gave a nice talk about the economics of P2P and ISPs; he's left Microsoft to work for Telefonica Barcelona, and has developed some insight from the ISP point of view.

Overall, I ended up with mixed feelings about this working meeting. It's useful to get people together to find out about what everyone is doing and to talk about high-level issues. Conferences already serve some of this purpose, though. Some of the value I got from this meeting derives from the fact I haven't been to a networking conference for a while (I didn't feel like traveling to Japan for SIGCOMM this year...). High-level issues don't necessarily get discussed at conferences, but it's also hard to get 50+ people together to talk about high-level issues and get any sort of agreement that wasn't already obvious. I'm skeptical that 3 such meetings are needed each year. However, the plan seems to be for the next meeting to be a graduate student focused meeting, which may be a good idea -- getting graduate students together to meet and talk like this seems like a potentially very interesting idea.

Going to the meeting will pay off, however, if it leads to any new collaborations. If any FIND people are reading this, and you want to add some theory to your work, send me an e-mail. (Of course, you could also go down the hall and talk to the theorist(s) in your locale, which I'd really strongly recommend, unless I'd be interested, in which case try me first!)

Monday, November 26, 2007

Introducing New Scientific Ideas, and D-Wave

Apropos of my last post on Digital Fountain is Scott's Aaronson's current report on D-Wave researchers giving talks about what's behind the hype of their building of quantum computers. For those who don't know the story, the short summary is that D-Wave Systems has claimed non-trivial advancements in the development of quantum computers, and many (most? all?) academic quantum scientists aren't buying it, based on the very limited evidence they've seen.

Why does this story remind me of Digital Fountain? I recall the early, early days going around giving talks about Tornado codes and their potential uses in networks, and in the beginning, the greatest skeptics were the coding theorists. One talk in particular, I remember, early on a very senior coding theorist insisted repeatedly that highly optimized Reed-Solomon codes could do anything we were claiming. The rest of the talk was a bit more difficult to get through after that argument. (I like to think by the end of the talk he thought that maybe there might be something new there...)

So is this to say that I think the academic crowd is being too hard on D-Wave? Absolutely not. It sounds like they're doing their job -- trying to figure out what's going on and asking tough questions. The point of my parallel is that the coding theorists had the right to be skeptical. (One reason for it was there was a huge language barrier, me not knowing what a "decibel" was, and them not really getting why linear vs. quadratic complexity was such a big deal. The divide being coding theorists and CS theorists has shrunk an awful lot this past decade.) It was our job to convince them that we had the goods. And we provided evidence with equations, papers, talks, and demos. While they took some convincing, the coding theorists listened to the evidence, and rapidly came around.

Here, the story seems to be (my interpretation!) that D-Wave is presenting painfully unconvincing demos and releasing not nearly enough information for experts to see if they have any new ideas. Then they're compounding this by excessive PR overstating what might eventually be possible with quantum computing. (There seem to be some arguments whether they themselves are doing the overstating, or uninformed journalists, in which case D-Wave is just failing to correct the press, but whatever.) Their excuse for this is that they're a private company so they have to keep their secrets. Understood! But they shouldn't then be surprised when knowledgeable academics studying the issue voice their opinion that the emperor has no clothes. I'm quite sure the scientific community has enough open-minded people that if they start producing convincing evidence, or give enough details on what they're doing so people can verify if the path they're taking is productive, they'll be understood and praised. Until then, the feedback they're getting is rightly telling them they have more to do.

Sunday, November 25, 2007

What's Up, Digital Fountain?

Every now and again, I get asked about Digital Fountain, the startup that initially grew out of work I was involved with on Tornado codes, a flavor of low-density parity-check codes. (The current codes being used are apparently based on Amin Shokrollahi's improved variant, Raptor codes -- the page has a link to the Trans. on Inf. Theory paper.) Unfortunately, I've been disconnected from Digital Fountain since the tech bust of 2000 or so, so I'm no longer privy to their internal workings. But the company indeed lives on. Every once in a while, I check for news, and I recently saw this positive piece on ZDNet, complete with a recent talk/demo from the fall Demo conference. Digital Fountain is making a push to get into IPTV.

So maybe someday I'll be watching IPTV using a Digital-Fountain enabled product.

Wednesday, November 21, 2007

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?

Sunday, November 18, 2007

David Parkes talk Monday, 4pm

David Parkes will be giving a talk on computational mechanism design in Maxwell-Dworkin G115 at 4pm on the 19th. This is what at Harvard we call the "tenure talk" -- it's a talk he gives giving an overview of his research and research area as he's coming up for tenure. If you're a theorist in the area and want to hear a perhaps slightly different point of view on mechanism design and work at the intersection of economics/cs (David proves things, but he comes from the AI side), you should come. Heck, if you're local, in any area, and interested in the economics/cs interface you should come. It should be a very nice talk, and it would be great to have the room full to bursting as a sign of support of David.

Friday, November 16, 2007

Should IP issues affect our research?

Since I've done some legal consulting, I've become interested in intellectual property (IP) issues, and the question of whether IP issues should affect my research agenda has recently occurred to me.

Let me explain. As an algorithmist, a major interest for me is designing algorithms that people will actually use -- perhaps not in the original form that I describe them in, of course, but that the ideas make it out into the real world. And while it is not my aim that every project I'm involved in should have a clear potential practical impact, it is the case that this goal guides my overall research agenda quite significantly.

IP issues have the potential to limit the practical impact of an algorithm I design. For example, suppose someone has a patent on SuperHashSchemeX (SHSX). (If you want something more specific, suppose Bloom filters were patented.) I might come up to an improvement to SHSX, or a better analysis of SHSX, but if the patent is written well, the patent owner may have rights controlling who could use SHSX, including my improvement. There may really be no hope that anyone else will actually be able to make use of my ideas, until the patent runs out, or unless the user is willing to buy a license. Indeed, unless I go through the process of obtaining a patent, it's possible that my work might simply add value for the initial patent-holder, and I've actually rewarded those who are keeping my work from being used.

Perhaps this wouldn't bother me if my theory blood ran pure, but I like being an "applied theorist". In my mind, this affects the calculus I use in thinking about what I should work on.

Should it? Has anyone actually run into this problem?

Monday, November 12, 2007

An Experiment in Viral Marketing : Buying Tickets Online

(Warning: the following post is highly crass and commercial. If that offends you in any way, please don't read on.)

Thanks to some friends who are working in Web marketing, I have a chance to try a viral marketing experiment right here on the blog. I have been give some discount codes for a new ticket site -- ticketheroes.com -- which offers tickets for sports/concerts/other events. Anyone can use them, at least until 1/1/08, so you can use them, or tell a friend to use them, or have a friend tell a friend, or whatever. According to that whole 6 degrees of separation thing, it's possible that everyone in the world could learn my discount codes, which by the way are:

MMBLOG1 [$5 off any ticket purchase]
MMBLOG2 [5% off any ticket purchase]
[Yes, you can only use one of them...]

To be clear, I am officially acting as a consultant for the SEM company that is trying to drive traffic to TicketHeroes. I am not getting a direct cut back from sales using these codes. (Though if this experiment is hugely successful, perhaps I'll try to negotiate one!) But I will get back data -- I'll get to see how many sales used the codes. (Don't worry, I won't get your credit card number.) I find this all very interesting. Can this little blog, focusing primarily on academic topics, help sell things? Really? I kind of doubt it, but hey, I remember thinking around the year 1999 that it would be a really impressive thing if Google became a 1 billion dollar company, so clearly I don't know as much as I should about marketing.

I've done my own checks and the site's prices look to be slightly less than or the same as other similar sites, even without the discount. So this should be a win for anyone looking for tickets, although of course you shouldn't trust me, you should compare.

Next post, we'll return to less crass, commercial topics, like how to re-finance your mortgage.

Saturday, November 10, 2007

Thursday, November 08, 2007

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.

Monday, November 05, 2007

Graduate Students, Socialize!

The discussion that in my mind connected breadth requirements to social networks reminded me of my time as a graduate student at Berkeley, where there were lots of informal social opportunities for graduate students to meet and talk. The CS grad student association had a weekly bagel/donut hour that was always well attended (mmmm...donuts....); the theory students arranged a Friday afternoon seminar (I believe called TGIF) where theory students would present something (a practice talk, some ongoing research, a paper they liked), no faculty allowed; there was a regular Friday pre-weekend grad student get-together that would be at a semi-randomly chosen local bar (usually upwards of a dozen or so people would show, with a high percentage of theorists, who didn't have to spend the weekend coding or running jobs); a grad student poker game broke out once a month or so (again, with a high percentage of theorists, who'd add complexity to the games).

Besides helping create a more pleasant graduate student atmosphere and experience, these activities let graduate students get to know more about each other and what they were doing. And I believe expanding your own work-related social network pays dividends in the long run.

I don't know what the current state of graduate student life is like these days, but if you don't think there's enough of this sort of stuff where you are, I encourage you, take action! (Don't wait for the department to do it; you'll do it better anyhow.) Try to get a grad student poker game going. Or a biweekly pub night. Or start an informal seminar. Or an open problems session. Or whatever it is you want to do, where graduate students can just hang out together, without faculty, with it being about fun, instead of or combined with work. Besides having more fun, you'll open up more opportunities for the serendipitous events in your work-life that lead to exciting projects.

Friday, November 02, 2007

Breadth Requirements

In our department we're looking at the class requirements for Ph.D. students, and in particular breadth requirements.

I'll state clearly that my opinion is that breadth requirements are a good thing. Breadth requirements for Ph.D. students are like vegetables for kids -- they don't always like them, but they're good for them. When I was at Berkeley the breadth requirements were reasonably onerous and I think they were very positive for me (even if, as contemporaries will suggest, it seemed like I slept through most of them). I especially think it's good for theoretical people to have a background in many areas of computer science outside theory, and classes are arguably the best way to get that background. And certainly I would argue that people in systems need some theory in their background.

I'd enjoy hearing arguments from the other side. You can argue that breadth requirements in general are a bad idea, or specifically that theory people shouldn't have to take classes in other CS areas (they should be allowed to just do all theory!), or that systems people shouldn't have to take a theory class. Any EE readers or readers from other areas should chime in with arguments based on their experiences as well!

Wednesday, October 31, 2007

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?

Monday, October 29, 2007

Consulting

I enjoy consulting, for several reasons:
  1. It fulfills a need to be more directly relevant to the real world.
  2. It gives me a chance to work with different sets of people.
  3. It allows me to learn new things and exercise skills that I don't necessarily use as a professor.
  4. It pays well.
I’ve consulted for research labs, startups, and larger companies, doing research, development, and expert witness work. I’ve been consulting since graduate school, and it’s an activity I’d recommend for most graduate students, once they’re comfortable in their research. I view the flexibility of being able to do research while still being able to take on consulting projects as one of the major benefits of being a professor.

Although I do know several algorithmists that consult at times, my impression is that the consulting culture is surprisingly small in computer science theory, even among algorithmists, and that it is much more prevalent in networking and EE theory. (The exceptional case I can recall is around the time of Akamai, where once it seemed like a sure bet, a lot of theorists hopped on the bandwagon for at least a short stint.) I generally hear people talk about consulting much more at networking and EE conferences than I do at theory conferences. Maybe it's just impolite to talk about it. Or maybe theorists don't consult much because most don’t have the skills people are looking for in consultants. Or maybe most theorists just aren’t that interested in consulting, and that's part of why they ended up being theorists.

Do you consult? (I'm particularly curious -- do complexity theorists consult?) If not, why not? Are my impressions about theory+consulting just way off base?

Sunday, October 28, 2007

Academic jobs this season?

I’ve already mentioned Harvard is doing a junior faculty search – although not specifically for a theorist. Any other faculty hiring announcements, either broad-based or theory specific? Or any new postdoc announcements worth repeating here?

Monday, October 22, 2007

Service to the Academic Community: Goals?

Except for the rare award (like the ACM-SIGACT Distingushed Service Award or Aaron D. Wyner Distinguished Service Award), our academic community does not appear to especially value service to the community. Research dominates our mindset. At the same time, on the whole, pleasantly the community seems quite conscientious about giving back. Somehow, conferences get run, workshops get organized, journal papers get reviewed, the NSF panels meet and make their bizarre decisions, and so on.

Strangely, I can't think of any time where a "philosophy of service" has been explained to me -- in graduate school or as a new faculty member, from the theory CS community or from my institution that employs me. Thinking about this, I find it rather odd. Surely, someone should be suggesting what's an appropriate level of time and effort to put into service, and where these efforts might best be applied.

(There is some advice I've seen in books for new faculty members. For example, Robert Boice's book Advice for New Faculty Memberssuggests that new faculty essentially spend as little time as possible on service activities, and make early service opportunities as self-serving as self-benefitting as possible. I roughly agree, but we should make this part of a well-reasoned philosophy of service -- the community should protect it's youngest members and help them flourish.)

I think this topic is ripe for community discussion, and some resulting general guidelines. People should have some guidelines as to what's expected -- what's usual and what's exceptional community service. (And to be clear, here I mean service to the scientific community at large; university service, for example, is separate.)

I'll start with two basic, over-arching questions. (I have more specific ones in mind, but I'll save that for the next post.)
  1. How much time should be spent on academic service activities? [My take -- 1/8 time, or at least one hour a day on average, for senior faculty. Less for junior faculty starting out, but increasing steadily toward that. Ostensibly, people in research labs should also be at 1/8 service time -- anyone know of any policies on that?]
  2. Should we be better rewarding service, and if so, how?

Saturday, October 20, 2007

Brief FOCS Update

I went to FOCS for the day of tutorials. Great talks by all of the speakers (Terence Tao, Dan Boneh, and Dan Spielman) -- and it seemed to me like a very large attendance for the tutorials. I understand slides and such will be put on the appropriate FOCS page soon, so rather than give detailed comments, I'll provide a pointer when they're up.

Also, I wanted to give a big thanks to the local arrangements team of Philip Klein, Anna Lysyanskaya, and Claire Mathieu, as well as everyone assisting them, since I know from experience that local arrangements is a thankless job. I found today's setup wonderful. The room at Brown was great -- perfect size, fine acoustics. Lots of food and refreshments were put out, and to save the conference money, it wasn't catered, but the local arrangements team brought stuff in themselves. (I arrived early and saw Anna driving up with a car full of goodies!) That's the kind of extra dedication that helps keep conferences affordable for everyone, at the expense of the personal time of the people who have to make it all run. So thanks again!

The FOCS setup has reminded me that I wanted to do a series of posts on the theme of service, something I'll try to get to this week.

Friday, October 19, 2007

Harvard Computer Science Hiring

We're eagerly looking for candidates in CS in all areas at the junior level (i.e., assistant profs). (Be sure to tell your non-theory friends as well.) Here's the ad for the search.

Wednesday, October 17, 2007

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.