Branding Your Research (and Yourself)

In honor of being at EC, a post on branding.

In theory, your research will be judged and appreciated based on its intrinsic quality, and your scientific reputation will follow accordingly.

In practice, unsurprisingly, branding helps, both you and your research.  I certainly wouldn't claim to be an expert, or even particularly good, at branding, although I'd acknowledge I've benefited from it throughout my career.  So you should take this as a starting point, rather than a final word on the subject (and comments are very, very welcome).

By branding I mean any of the sorts of things that might be considered marketing.  Perhaps one of the most basic methods of branding involves something as simple as choosing project names.  Well-chosen project names are a simple way to get people to remember your work -- when we hear PageRank, Chord, smoothed analysis, or XORS in the Air, for example, it resonates;  they've become lasting brand names.  Picking good names is hard, though -- it's easy to go overboard, or come up with something that just sounds ugly.  (I should note that networking people, perhaps because they build specific systems, seem much better at and more aware of this kind of branding than theory people in my experience.)  I'm not sure if cool-sounding project names can help you get research funding (Robobees!), but my guess is it doesn't hurt. 

Another basic approach is to become associated with a certain type of research -- especially, if possible, if you've started a chain of research, although you can certainly become well-associated with a line of work you didn't initiate.  Often this is a certain subarea -- "they do online algorithms", "they do network coding" -- or can be a certain technique "they're expert in their use of martingales."  Perhaps best, early in your career, is to be associated with something fairly specific -- "they work on cuckoo hashing."  This is why, as a graduate student, you're very strongly encouraged to find a thesis topic where you can write multiple closely thematically related papers --  it helps you to get known for something, which is an important benefit in a competitive job market.  One can argue whether it's really a good thing that people's work is reduced, at times, to such a shorthand, but when dealing with dozens of potential candidates, having a natural and memorable label is truly helpful.

Indeed, the other major time in academia that branding seems important is when you come up for tenure.  I was explicitly asked what I was "known for" when I came up for tenure.  (Hint:  if what you're known for is just your PhD work, that's usually not a good sign.)  It makes sense, when your case is being prepared for a broader audience outside your immediate field, that your work be summarized in your tenure case -- preferably into key "brand names", easily describable by key words and phrases (power of two choices, low-density parity-check codes, Bloom filters, etc.) --  that will match the summaries that come in from the external letters.  This follows the principle (that I try to emphasize to my students) of making it easy on the people who are grading you.  If the letters match your case description, that's good positive reinforcement.    

Of course, another aspect of branding is standard self-promotion -- giving talks, for instance.  Or writing a blog -- shameless, but effective, self-promotion.  (I definitely noticed I was invited to give more talks after starting the blog.)  Writing a blog is certainly not for everyone, but you should find other ways of promoting yourself and your work.

One perhaps underestimated and lesser-utilized but powerful branding method is to write a survey -- or, if you're up for it, a longer treatise, or even a book.  I've written several surveys, and besides being useful for myself, I've been amazed how many people seem to read (and even cite) the things.  It's possibly been my most powerful consciously used branding tool (outside the blog).  I'm already thinking now of the next survey I want to write.     

An eventual goal, of course, is to obtain many brands that are associated with you -- different research topics, in potentially different areas.  This is helpful because of the obvious reason: if you're known in multiple contexts, you'll get more chances for any specific individual to know you.  Of course this takes time.  As a graduate student, it seems to make more sense to work on developing a single, strong self-brand rather than many.  (That's not to say that you just work on one thing -- some breadth is generally appreciated and looked for at hiring time -- but there's usually a clear focus on one line of research.)  Once you become a faculty member, you can start developing more brands.  If you have many students, this may happen naturally -- each student will (or at least should) be trying to develop their own brand, which you may be associated with as an advisor.  In some sense, your students can be a brand extension, although hopefully they can also become their own independent brand.  

I've been fortunate, I think, to have over time apparently developed multiple brands in multiple areas.  It's fun for me that when I visit someplace to give a talk, the theory/networking/information theory people all seem interested in talking with me.  One thing that's clear is that people see your brand from the context of their own work, which is worth keeping in mind.   Sometime after I wrote my survey on power laws (and another associated paper on power laws), Barabasi (of various book fame --  Bursts and Linked) invited me to come give a talk to his group.  He nicely introduced me as being most famous for my work on power laws -- something that was, I imagine, certainly true from his perspective.  People will generally know at most one or maybe two of your brands, and that's fine.


So what are the downsides of branding yourself and your work?  You do run the risk of getting pigeonholed, like a child star, known for a small bit of your larger body of work.  I'm still widely known as the "balls-and-bins" guy.  Worse yet, you may start to believe yourself that you're tied to the area you're known for, and become afraid of trying something else.  Becoming "the expert" in an area means you'll get asked to review many of the papers in that area.  After all, all the papers cite you, and that's what the editors see.  And, of course, branding is a time-consuming activity, that takes patience and energy.  Still, for most people, a little conscious attention to research branding efforts can probably go a long way.  

I'm not sure how far this analogy can go.  Can you develop brand loyalty for your research?  I think so -- there are certainly researchers I try to follow regularly.  Can you re-position brands?  Parallel algorithms are new and exciting again, right?  Are there any "iconic" brands in research?

I'm sure some of you think spending a whole post on branding is somewhat silly.  For the theorists, let me point you here.

EC Day 1

EC is an interesting mix of theory/AI/economics and many other things as well (data mining, social computing, user interfaces....)  Definitely a bit of a hodgepodge, but interesting in its variety.  If you don't look at the titles/abstracts ahead of time, you never quite know what the next talk will bring.  (Maybe I should be looking at the titles and abstracts ahead of time...)

Some quick highlights

Giorgos Zervas gave the talk on our Swoopo paper. 

Rahul Sami gave an interesting talk based on the idea of dealing with external incentives in mechanism design settings.

Ramesh Johari gave a talk about a simple model meant to abstract the competing effects of network effects and congestion. 

Sven Seuken talked about market design and analysis of a P2P backup system.

I'm sure there were other interesting things, but I was in and out of sessions at times.

STOC 2010, and Some Business Meeting Notes

STOC 2010 appears to be running quite smoothly.  I've been popping in and out -- the problem with being a local is that I actually have to go home at reasonable times (and stop by the office quickly).  While nominally (thanks to Lance) I was appointed Conference Chair, my role, happily, was minimal.  Great thanks to the efforts of the Microsoft Local Arrangements Team -- particularly Paul Oka -- and also Yael Kalai, Adam Kalai, hosts Jennifer Chayes and Christian Borgs, and anyone else I'm forgetting.  (Personally, I'm now all for a Microsoft team managing local arrangements every few years... all in favor?)

Thanks to everyone who has offered condolences for my new position, and special thanks to those who said they'd hope my scientific career might revive a few years hence. 

A quick word on the business meeting.  I wasn't actually there, but I understand Lance briefly discussed "The Future of STOC."  Let me briefly give my take, as I understand there might have been some confusion.

1)  Several of us on the SIGACT executive committee have been concerned that STOC seems to be at best stable (and perhaps slightly deteriorating) in terms of attendance the last several years, even as our field is ostensibly growing.  Perhaps, we think, STOC/FOCS are not adequately fulfilling their roles as the central, flagship events of the theory community.  (Needless to say, given this year's attendance, perhaps things are brighter than we think.)
2)  So we think about it.  For example, some of you might recall my wacky Double One, Half the Other post from November. 
3)  Lance comes up with an even more drastic proposal, and tries to get some feedback on it from targeted members of the community.  I believe he tried to explain this proposal at the business meeting.  To be clear, the feedback before the meeting was largely very negative;  although many people think things could be structurally improved, there's a lot of different opinions as to what form that should take.  This proposal was never meant to be on the table at the business meeting.
4)  The one thing that DID seem to have reasonably widespread support is that we could accept more papers.  We still have some room if we made it a full 3-day schedule.  STOC acceptance rates have dropped from generally well over 30% in the 1990's and early 00's (some years it was over 40%!) to 25-30% the last few years.  While upping the number of papers is, admittedly, a small delta, and not likely to change some potentially larger systematic issues with the conference, it seems like a good idea -- it should get some more people to come, and perhaps will allow a bit more leeway in terms of what is accepted.  Moreover, if people liked the change, then perhaps we could think of further changes (a 3.5 or 4-day conference?  triple sessions like SODA?  your idea here?) that could further open up the conference.  

So the SIGACT EC came up with the proposal that we advise next year's chair that, as long as the paper quality warrants it, there's no reason to aim for about 75-80 papers (the apparent "target" of the last many years) and we would be happy if they might aim for 85-90 papers.

Again, I wasn't at the business meeting, but I heard even this modest proposal did not receive enthusiastic support.  I'm starting to get the feeling there's a non-trivial minority that thinks the conference is going just fine, and are in principle against any change.  I can certainly understand trepidation at radical change, but I can't see any reason not to try this modest experiment, which seems to have little to no downside and some reasonable possible upside.

So feel free to explain YOUR opinions in the comments.
     

Conference Attendance : How to Keep it Strong?

In honor of the STOC business meeting coming up shortly:

STOC, CCC, and EC are all apparently poised to have very strong attendance this year -- from what I understand, greatly improving over previous years.  Why?

I suggest two obvious reasons:

1)  Location:  Cambridge is clearly a great location, with plenty of major universities and research labs nearby, and a major airport readily accessible.
2)  Co-location:  From what I can tell, having all these conferences in the same place in the same week is helping boost attendance for all of them.

Can we take something away from this for future years (please!)?  Having conferences in easily accessible, researcher-rich cities is a good idea.  ("Geographic equality" is overrated.)  A reasonable amount of co-location (arguably less than a typical FCRC), appropriately managed, is quite desirable.  Let's test out these principles over the next several years as we try to arrange our conferences...

Announcement: Matt Welsh Tenured

I'm very, very pleased to announce that Matt Welsh's Harvard tenure case has been successful.  

There's a number of wonderful things I could say about Matt and his work, but I'll limit myself to two highlights.  Matt is well known to be a leader in the field of sensor networks/distributed systems, but his work particularly stands out for his ability to look at how these technologies might be used outside of computer science.  In particular, he's worked on sensors for medical care (the CodeBlue project and the Mercury project) and for "big science" (monitoring volcanoes and monitoring weather/pollution).  At Harvard, because CS is smaller than at some of competing institutions, we want professors who are not only leaders in their area, but who can also take advantage of Harvard's breadth and other strengths, with an eye toward showing the world just what CS can do.  Matt is an excellent example of the type of scientist we're looking for.

Outside of his science, Matt is a great colleague.  When I think of a word to describe Matt, "leader" comes right to mind.  When Matt sees something he wants to improve in our program or how we run things, he studies it, presents his opinions, garners support, and finds a way to make the change happen -- often taking on much of the required work himself.  He has both incredible energy, and the ability to persuade people to follow where he wants them to go, two qualities I associate with leadership.  Because of this, I know his presence will benefit CS at Harvard in countless ways in years to come.

Congrats to Matt!  (Now go read his blog...)

SIGCOMM Travel Grants

I was asked by the SIGCOMM program chairs to remind everyone that there are travel grants available, especially for students, postdocs, and junior faculty.  Since the conference is far away this year (India), they've tried to get a lot of travel support.  They've extended the deadline to 11:59 pm PDT on June 12, 2010.

Information can be found here.

Will Google Buy ITA?

As long-time readers of the blog know, I am a fan of ITA software, the company with the fare-finding technology and search engine that powers Orbitz and several other airline web sites.  Indeed, for my recent trip to Bertinoro ITA saved my grants several hundred dollars -- they found a pair of flights involving two separate, currently non-partnered airlines at a price that couldn't be duplicated on several other sites I tried.  (The flights should, I hope, even meet NSF's unwieldy international flight rules.)

For at least six weeks, there has been buzz that Google was looking at buying ITA, for the tune of roughly 1 billion dollars.     But not much has been heard of late, with possible reasons being described in this recent post at tnooz.  Indeed, I ran into an ITA person I know "on the street" a while back and asked when I could officially congratulate them, and was politely brushed off.  

It's not clear to me if Google/ITA would be a match made in heaven or not, but I admit I'm eagerly awaiting to hear the news (one way or another).  I would place ITA in the category of companies that show that cool things that can come out of smart algorithms and data structures (see this old writeup), so I wish them success.  I think reaching the billion dollar selling point would certainly be one reasonable measure of success.

Don't be surprised to see more of this story in the news in the future.   

What Work to Give Up?

I'm not yet sure how many hours a week being a Chair (oops, "Area Dean") will chew up, but I think it's safe to say it will be a non-trivial number.  I'm generally a fairly busy person, and while I imagine I'll have to (somewhat happily!) cut down on my bad TV-watching habit, I'll also be cutting back on some of my other work responsibilities.  Obviously, as much as possible, I'd like "research time" not to be part of those cutbacks.  (I've heard that's a problem with this job in general.)  As Matt's blog post on secret lives of professors calls attention to, professors are just naturally overloaded;  it's good to stop and think once in a while about what you can happily and safely do less of.

So, what could you give up to get yourself back a few hours a week?

For me, the blog is (sadly) one of those things.  Here's some other things on my list:

1)  Giving up an editor position:  I'm going to step down as an editor of SICOMP.  I've found I really don't enjoy being an editor -- the only thing worse than reviewing a paper yourself is having to cajole someone into agreeing to review a paper and then, after getting reminded yourself by the automatic system how long it has been since the paper was submitted, having to go back and cajole the reviewers into actually finishing the review.  I'm happy to give it up.  On the other hand, it won't save me so much time;  I dislike the job so much I already avoid spending time on it now...

2)  Fewer PC committees:  I'm generally a bit too friendly about agreeing to serve on PCs.   I counted and it looks like I've done about 35 over the last 10 years.  Some have been small and some have been big, but that seems, from what I can tell, to be more than average.  (What's the "average"?  Is it different for networking people than for theory people?) 

I don't want to give up on doing PCs completely.  I find they're fun and interesting.  But I think I'll cut it to 1 or 2 a year while on the job.  Strangely, I'm most likely to say no to "small" conferences (like FUN, or ANALCO, say).  They take less time, but I find they're less fun and interesting to do. 

There's one thing that would definitely get me to a PC.  I chaired STOC last year, and think it could be fun to instead (co)-chair a networking conference.  Hint, hint, hint, powers-that-be...

3)  Less reviewing.  I seem to get asked to review papers a lot.  (In part, I suppose, because I'm "well-branded".  If it says "Bloom filter" on the title, and I didn't write it, odds are it's being sent to me.  To a lesser extent, that's also true for "cuckoo hashing", "deletion codes", and things related to the power of two choices.  I aslo get lots of things related to various flavors of LDPC codes and power laws.  Like other bloggers I hope to do a post on "branding" in the future, but this is one of the downsides.)

I've gotten much better about saying no to reviewing since tenure, and even moreso since our third child was born.  But I'm sure I can do better about saying no.  (And I'm sure I'm still doing more than average.)

4)  Less "other university work".   I'm on one or two university committees that don't take much time but aren't really important.  Good time to drop those.

Looking at all these things, it's clear I'm aiming at reducing other service activities, which happily makes sense.  Since serving as Area Dean is really a service activity (for Harvard), other service activities are the first to cut in its place.  As much as possible, I don't want my home life, research, teaching, advising, and consulting time to suffer. 

Bertinoro Day 3

Since I left, Andrew McGregor tool over and has posted a summary of day 3 on his polylogblog, which is also now added (at the top!) on the bloglist at the right.

Bertinoro, Day 2

Bertinoro is a really beautiful city.  I just felt like saying that.

Today's talks:  Geppino Pucci talked about Bluetooth networks, modeled as a variation of random geometric networks (points randomly distributed in the plane, connections to points within some radius, with Bluetooth you only connect to a bounded-size random subset of your neighbors) -- talk based on the ESA 2009 paper I believe.  Rasmus Pagh talked about data mining (here's one of his papers on the subject), Graham Cormode talked about streaming verification of massive computations covering several of his recent papers on the theme (including this one), Andrew McGregor talked further about stream computations and "detecting dubious data structures" -- starting with how do you check in small space from the transcript of operations that your priority queue performs correctly given that is starts and ends empty (paper here), Tamas Sarlos talked about sparse random projection (paper will be at STOC next week), and Gagan Aggarwal talked about weighted online bipartite matching (generalizing the well-known KVV algorithm for online bipartite matching).

Sadly, the rest of the talks will have to go unblogged (by me at least) -- I'm leaving the workshop unreasonably early in order to get a few days of home time before STOC/EC/ISIT.  See you all there...

Personal News : "New Job"

Since it's more or less been publicly announced at this point, I may as well announce it here:  starting July 1, I'll be the new Area Dean for Computer Science at Harvard.  Very roughly speaking, academics from schools that use a standard vocabulary (unlike Harvard) can translate that to "Chair" if they like.  I'll be filling the shoes of Greg Morrisett, who has been doing a fantastic job.  Indeed, from my standpoint the worst part of taking the job now is that Greg has done such a great job he'll be a hard act to follow.  (But he's served his time, and will be enjoying a sabbatical!)

The new role isn't really a surprise.  At Harvard, we more-or-less take turns in this position, and I knew my turn was probably coming next.  The standard is a 3-year stint and that's what I'm expecting.  We have a faculty with tremendous leadership depth so I'm not worried about getting stuck with the job.  Indeed, one of the great things about our faculty is that we have so many people that can do the job well, and at the same time we have nobody who really wants the job.  (An old academic saying, apparently, is to beware anyone who actually wants to be chair.)

I'll undoubtedly self-indulge and write a few more posts about my thoughts on the job before actually beginning it.  But one thing that's clear is that how I spend my time will change -- at least, that's the impression I get by the happy jig Greg breaks into these days whenever he sees me -- so it's a good time to reflect on that.  And one of the first things that was clear to me is that I'll be shutting down mybiasedcoin, probably sometime in August.  Just to be clear, there was no pressure by anyone at Harvard to do so -- indeed, Greg encouraged me to keep it going -- but I think it's time.

The reason is a combination of things.  The biggest is that the blog takes time, of course, and I expect to have less time available.  I also admit to being a bit burned out after doing it now for 3 years.  (It's been that long?)  Finally, I worry that the job will involve all sorts of things I shouldn't write about, but might want to, which could be frustrating -- and, potentially, disastrous.  (Nobody has called me out on this, but in the blog I write basically nothing about my consulting work -- even though I might like to -- because in most cases that would be inappropriate.  I figure the same will happen with parts of the new job.)

There are conferences (STOC, EC, ISIT) to blog about in the immediate future, some papers in the pipeline I hope to have a chance to discuss, and probably some issues in the back of my head that I'd like to blog about before stopping.  That's a couple months more of posts. 

I don't feel too bad about stopping -- there are plenty of other CS blogs out there, other voices to be heard.  If I feel the need, I'll guest post somewhere when I have an opinion.

Which, obviously, I often do...

Blogging from Bertinoro

I'm here at Bertinoro (a beautiful, out-of-the-way, small town in Italy) for the 2010 version of Random GRAALS (= graphs and algorithms), a workshop that we've been having every few years, usually with around 30 or so people, which provides an opportunity to hear some nice talks, and gives a bunch of us an excuse to go to Bertinoro.  Sadly, I'll have to leave a bit early, so I can have some "home days" before STOC/EC/ISIT.  Busy start of summer.

Leslie Goldberg and Mark Jerrum started off with a joint talk on the complexity of certain graph counting problems, focusing on the connections between the hardness of approximate counting of independent sets on bipartite graphs and the hardness of computing the Tutte polynomial at various points.  They (along with others) have been looking at variations on this theme for quite some time;  there was a very nice bit about developing gadgets for randomized reductions by making using of random graphs with "bistable" characteristics, specifically 2nd order phase transitions, that seemed like fun.  Aris Anagnostopoulos talked about Approximation Algorithms for Dynamic Data -- for example, suppose you're trying to keep a set of item counts sorted, but the counts are changing over time, so as you do comparisons to sort, the underlying ground truth can be changing.  The data changes slowly enough that it doesn't change arbitrarily over time steps, but instead in a limited fashion;  however, it changes fast enough -- or comparisons are expensive enough -- you can't just resort everything each time step.  Uriel Feige talked about hat puzzles on graphs, with a nice collection of open problems on this generalization of the standard hat puzzle.  I talked about random stuff I've been doing, including the improved analysis of the lossy difference aggregator, and the Carousel paper on network logging that appeared at NSDI.  I then forced the audience to sit through a brief version of our talk on Swoopo -- which will be presented at EC next week.  Berthold Vocking talked about combinatorial auctions for secondary spectrum auctions, looking at models of conflict graphs and independent sets.

I enjoyed all the talks, but I have to say, as always I'm impressed with Uri's talk -- he somehow makes everything seem approachable and fun.  

Now we're going out for what, I assume, will be a wonderful Italian dinner.

Extension Results

At the start of semester, at one point I had 48 people signed up for my extension Algorithms and Data Structures course, which I said from day one would not last.  (The extension class is for Distance Education students, offered by Harvard's Division of Continuing Education;  students see recorded versions of the Harvard class lectures made available online, and I run the class very much like the Harvard class.)  17 made it through to get final grades.  That's well within the normal range.

My reviews from the extension school have generally, over the years, been satisfactory.  As I usually have minimal personal interaction with the students, I've never expected great reviews.  Strangely, for the last two years, while my teaching review numbers for the regular Harvard class have significantly declined (due to a vocal minority that appears to not enjoy the class), the numbers for the extension class have significantly risen.  Perhaps I should be concluding that I'm better on camera than in person?

Really, I'm at a loss to explain.  Obviously, the extension reviews are from self-selected survivors, so they're more likely to appreciate the class.  In the regular class, I notice that the poor reviews seem to come almost exclusively from those who are taking the class because it is (almost, but not really) a requirement for being a CS major -- hence, possibly, from people who don't really want to be there in the first place.  I might think extension students have lower expectations, in terms of grades.  For administrative reasons they really want to get at least a B in my class, and I think they're prepped to understand coming in that that's a difficult goal.  I should point out that most -- indeed, nearly all -- of the 17 left at the end got a B or higher.  Most also come in quite aware of the gaps in their background and work very hard to make up for them.

However, none of these things seem to explain the delta over previous years, and in particular the difference in direction in the delta between these two groups of students.  Go figure.

In any case, the extension students from CS 124 this semester should be very proud of themselves.  I believe my class is one of the more challenging undergraduate Algorithms and Data Structures classes at any university -- extension or otherwise.  Many (most?) of these students have jobs, families, and other responsibilities that make taking any class extremely difficult.  They should know that I'm impressed by them, and I hope my class turns out to be a useful experience for them.

Giving in to Student Demands

I received my student reviews today, and while I could easily post days' worth of discussions on them, suffice to say there's a non-trivial minority of students who seem unhappy.  While it's entirely possible that these students simply do not like my personality (which is unlikely to change to suit their needs) and hence would not like the class regardless of what I do, I'm attempting to reflect more constructively and find things to change next year.  (So, in some ways, this is just a note to myself that I happen to be sharing.) 

One change I guess I'll have to make is to officially label one textbook Mandatory.  I suggest both the standard Introduction to Algorithms and Algorithm Design as useful optional textbooks in the syllabus, and instead provide students with my lecture notes.  But several complain they find the lecture notes insufficient, so I'm guessing they don't understand that optional does not actually mean "unnecessary for everyone", and the best solution I can come up with is to make a book mandatory.  I can see other uses for this, such as assigning problems from the book as good review problems or problems to cover in section, so perhaps it's really a win for everyone.  If anyone cares to offer any insight into which of these two are most useful (keeping in mind I'll still be using and making available my lecture notes) please advise in comments.    

(This subset of students also complains that the lecture notes haven't really changed since I first wrote them about ten years ago, which is true enough, although I don't believe that, for example, Prim's algorithm has changed substantially in that time either.  The latest edition of Intro to Algs seems to be from 2009, while Algorithm Design now goes all the way back to 2005, so maybe Intro to Algs should win based on newness.)

A number of students also complain about the midterm.  Not just that it's too hard -- which is fine for them to complain about, it is indeed quite hard, although I personally would label it "just right" -- but that it's the same day an assignment is due, just before spring break.  Somehow, having the midterm after spring break, or before they've done an assignment on the material, has just always seemed like a bad idea to me, but it's clearly not working for them.

I think I've found a creative solution, which is simply to abolish the midterm.  This has many advantages beyond dealing with the complaints above.  For example, the past couple of years another faculty member has complained about my choice of midterm day, because they wanted to schedule their midterm that day, and didn't think it would be appropriate for the students taking both classes to have to take two midterms.  So now I can yield this midterm day.

Further advantages come from my midterm replacement idea.  I still want to have in-class assessment, so instead of a midterm, I'll break it up into shorter in-class quizzes.  I'll get a more timely idea of what students aren't understanding; we can go over the quiz problems, giving the students more feedback (partially solving a different complaint, that because I don't hand out answers to problem sets, students don't get enough feedback);  and now class attendance will be essentially mandatory.  I'll let students drop their lowest one or two quizzes, so if they miss a class quiz, they can use a drop, but students will have to get to class more often.  (Besides giving lecture notes, my lectures are taped, so currently some students often don't come to class and catch the video later.)  The biggest downside is that I'll have to drop some material to make time for this approach.  I have some fun lectures at the end about a Least Common Ancestor algorithm and suffix trees (maximal palindromes in linear time!) that I'm sure I'll have to drop at a minimum, but even I admit those are a bit esoteric for a first algorithms course.  I can always make the notes available for the interested.   

I imagine these changes will fail to please everyone.  But I think they're worth a try.  As I reread this, I recognize this might all sound sarcastic, and while I've sprinkled in some sarcasm in the discussion, these do seem like things I'll plan to do next year. There are also other changes I'll try to implement with the TAs -- a common complaint is that they can be too picky on details in grading (true enough) and that more math review is needed (certainly possible, best done by splitting up sections into super-advanced/standard/math-phobic?).  Then we'll see if any of this effort pays off in next year's reviews.    

Links to Look At

Matt Welsh has what he tells me is his most-read post ever about The Secret Lives of Professors.  I'll help promote it here, but save my commentary for the comments there.

FemaleScienceProfessor has had two great posts this week.  Yesterday's post was about the Canada Excellence Research Chair program -- "to attract Canadian and international leading scientists" in critical areas of research -- that gave a lot of money to 19 chosen faculty -- all men.  Today's post raises a challenging question -- under what circumstances would you retract a letter of recommendation?

As many other have noted, Martin Gardner has passed away.  Here's his Wikipedia page. 

As the 2nd Innovations in Computer Science page is up, it must also be time to remind people of SLOGN. 

A blog post on the CCC at 3 years. 

Grade Inflation?

I know Harvard is supposed to be famous for its grade inflation, but that's not generally the case in my class (and, I think, for our CS classes in general).  Having recently turned in grades, and having already started getting concerned notes from students regarding grades, I'm curious:

For an undergraduate class ---

What's the median grade you give?

Does it vary significantly from year to year?

Does the class size matter?  (Do you tend to give higher average grades in smaller classes?)

Just curious.

ACM elections reminder

I was asked to remind everyone that if they want to vote on the ACM elections, the deadline is May 24th.  Here is the official ACM election page.  You might note that Salil Vadhan is running for Member at Large...

In particular, a blog reader asked me to point to this position page on the candidates' opinions on open access, which is a fairly important topic for the future.

Harvard News Items

Some highlights:

1) From the Crimson:  "An undergraduate has been dismissed from Harvard College after allegedly hacking into online accounts of the teaching staff in his courses." 

Makes me wish I was still on Faculty Council; I'm trying to figure out how the student "...designed a website to obtain the Harvard University IDs and the personal identification numbers (PIN) of his instructors."  (Designing the website is easy;  how did he get his instructors to log into it?)  I'm still trying to figure out if those antics are more or less impressive than the former Harvard student who sent in completely bogus data and recommendation letters in all sorts of various applications.

2)  Here's two articles (USA Today, Business Week) about the IRS looking into university spending, and in particular whether rich universities are hoarding endowment money.  The idea that universities who are spending under 5% should be encouraged (or forced) to do otherwise probably seemed a lot more compelling back in 2007-2008 when apparently they were surveying the universities about their spending;  with some schools (Harvard, Princeton) having to payout 6% this year to deal with recent losses, I'd imagine it seems less compelling now...

I've heard most endowments have made up a lot of their losses this year.  Harvard, ever a black box, has not released any information I'm aware of... anyone out there know more than I do?

3)  Various articles out (here's one from the Times Online) about the very negative portrayal of Facebook's Zuckerburg in the upcoming Facebook movie "The Social Network."  I'll probably have to go see it, if only to see the scenes with the Harvard Professor (check the IMDB credits) -- supposed to be, from what I hear, a representation of our own Matt Welsh.

Robobees Redux

While I intentionally try to avoid the political on this blog, I did make an exception previously when I heard that the Harvard Robobees project had made #1 on Sean Hannity's "List of Government's Most Reckless Spending," because that's downright stupid.  I've actually noticed that they've got the transcript from his show about this online.  (The video is also available here.)  Let's see what they actually say:

Begin Transcript:

And finally, we are here, and No. 1 will shock you. For that, we go to Ainsley Earhardt, who is standing by in Cambridge, Massachusetts, tonight — Ainsley.
AINSLEY EARHARDT, FOX NEWS CORRESPONDENT: Sean, No. 1 brings us here to Harvard University. This school got $9.3 million in stimulus money to build flying robotic bees, which they hope will one day help monitor traffic and even pollinate crops. We were in the community today, and this town was buzzing.
(BEGIN VIDEOTAPE)
UNIDENTIFIED MALE: Probably isn't going to stimulate the economy in the short term, which is what the stimulus package was supposed to do.
UNIDENTIFIED MALE: I don't think Harvard is doing anything that's wrong or improper. And I work with this organization a lot, and they do a lot of great research.
UNIDENTIFIED MALE: It seems like a project like that, while certainly admirable, and could definitely contribute in some way in the future, would probably be best put on hold for a while.
(END VIDEOTAPE)
EARHARDT: Did this$ 9.3 million project create any jobs? Well, according to Recovery.gov's Web site it created 1.66 jobs.
Well, we called Harvard, and they did give us a statement, and we're reading that, in part: "The three percent of stimulus funding provided for research was not only intended to create jobs immediately, it was also intended to stimulate economic growth, which is precisely what science funding does.
Designing and developing miniaturized flying robotic instruments that will prove useful in any number of ways, including surveillance applications on the battlefield and in weather forecasting, is an extremely important project."
So Sean, no one says that this project is not important. Folks here are just wondering how badly it will sting.
Back to you.
HANNITY: And thanks, Ainsley.

End Transcript.

Gee, you'd think they'd be able to come up with more damning things to day about the project, given that it was #1 on their list.  I'm actually disappointed reading this.  The only "shocking" thing about it is how little negative they actually say.  It sounds like some interns made up the list, decided robotic bees sounded goofy so they should put it up at #1, and then when they actually did even a little digging, realized they couldn't say all that much bad about it.  Even if one chooses to subscribe the usual tropes that the fringe (or not-so-fringe) right wing doesn't understand or care about science and technology that might range from useful to vital for our food supply, and that the only "good research" is weapons research, there are so many obvious potential military applications for such technology that they can't even make that sort of argument against this research project.  The only thing they seem to say is, "Well, this was part of the stimulus, how many jobs did it create?"  First, I'm not clear that the Expeditions budget directly came from stimulus money -- perhaps someone with better knowledge can clarify that?  But even if it did, Harvard's response statement seems quite appropriate.  

For a more reasonable take on the project, you could look, well, just about anywhere, including Engadget, Electronics Weekly, Network World, and several others.  Heck, even Robot Armageddon had a more reasoned take on the work (and they're worried about, well, the forthcoming robot armageddon). 

What's sad, though, is how often Hannity's list -- and the poor thinking behind it -- has been copied and passed around through the web.  A little looking around on Google shows it's been repeated probably hundreds of times in various places.  Clearly a lot of people have seen it, and probably many aren't inclined to get actual real information on their own.  While I haven't heard of any actual negative impacts on the Robobees research group, I think it's best for the community to be vigilant against this sort of ridiculous attack -- because, in the end, it could affect us all.  

The Value of Experiments

Several days ago Lance wrote about "Is Complexity Math or Science?", and in that context wrote "We don't do experiments...", which has caused me to overreact.

I'm not sure who he meant by "We" -- I guess complexity theorists -- but I found the statement very strange at the time.  I do experiments all the time.  (Note:  Here I am considering computer simulations of various sorts as "experiments".  Some people may quibble at this, but since it seems ALL THE REST OF SCIENCE is moving toward increasing use of computers, including and perhaps especially computer simulation, I think it would be odd not to call a computer scientist running a simulation an experiment.) 

For example, a couple of days ago, I thought I had proved something about random sequences for a project I'm working on.  I asked the graduate student on the project to code it up to check my work -- I often sanity check proofs with simulation code when I can -- and he shipped me some results that seemed surprising.  They were consistent with my proof, but effectively showed that things behaved even better than I had proven (or expected). 

So on the car ride home, I thought about it, and came up with what I think is a nice proof that explains what the student found in the simulation experiments.  This improved proof will end up in the eventual paper, I'm sure. 

While I wouldn't call myself a complexity theorist, it seems to me the results I'm working on here are in the class of complexity results -- I'm trying to show that certain permutations have certain properties with high probability, and I'm showing it by developing an algorithm that allows me to prove what I want.  Perhaps that's sufficiently far removed from "complexity theory" that some people think it doesn't count, but then it seems you'd have to throw the whole probabilistic method out of complexity theory, which seems strange to me.

My point is that the actual use of computers -- for example to simulate processes in order to sanity check proofs or develop insights and conjectures -- is part of how I do my theoretical research.  While certainly that approach might not be for everyone, I have deep concerns when a major-blogging-theorist says something like "We don't do experiments..."  I worry that increasingly that computer science graduate students in theory are loathe to actually use computers, and indeed that this is part of a broader problem that theory students specialize narrowly so early they don't get exposure to and an understanding of the rest of computer science.

So I'd just like to say, I personally find experiments very helpful. 

Another Book on Networks

Another book on networks, namely Networks: An Introduction, by Mark Newman, will be available in about a week or so.  Mark is known to many in the networking community;  though he comes from the physics side, he has worked with computer scientists such as Aaron Clauset and Cristopher Moore.

The Easley/Kleinberg book Networks, Crowds, and Markets: Reasoning About a Highly Connected Worldstill sems to be due out at the end of July. 

Complexity of Distributed Systems, Market Crash Style

Apparently, the stock market crash of 5/6/10 was not, as originally thought, due to a "standard" human/computer error where someone meant to sell a million shared but instead entered billion.  (Although, heck, that's an interesting enough possibility to think about on its own.)  Instead, it seems more like it was the result of unforeseen interactions and feedback between the market protocols and the computerized trading systems, running at high computer speeds, without a human in the loop to act as a brake or failsafe.  See, for example, this CNN post and this WSJ blog post, and dozens of further articles in the weeks to come.

I can't help but think that this should inspire some computer science research.  Let us take as a given that these unintended interactions, causing some stocks to be sold for pennies, should be viewed as a mistake.  How do we design a system that avoids such mistakes, with the least impact on the users (who are, clearly, in this case self-interested agents)?  Can we do so without humans in the loop, or is there a role for a human in the computerized, algorithmic trading world?  Can we develop a system whereby we could check for potential problems of this sort by having the big traders provide information about their trading strategies to some centralized agency, but in a way that no actual (or minimal) information about their trading strategies is actually released in the analysis?

If this isn't a motivating example for distributed systems/algorithmic game theory computer science research, I don't know what is.

Aldous/Diaconis: Longest Increasing Subsequences

For some research I'm currently doing, I ran across a truly wonderful "old" paper,
Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
by Aldous and Diaconis, which appeared in the Bulletin of the American Mathematical Society back in 1999.  It's easily findable online.

The fun in this paper is that it highlights the probabilists' notion of reduction, which is similar but slightly different from the standard CS notion.  Generally, it involves taking one process or class of objects and mapping it (usually bijectively) to another process or class of objects that can be analyzed.  And longest increasing subsequences, as it turns out, can be mapped into lots of things.  For example, a standard connection is with greedy patience sorting.  Here's the example from the paper.  Take a shuffled deck of cards:

7 2 8 1 3 4 10 6 9 5

Greedy patience sorting puts the cards into piles using the following rules:
1)  A card can be placed on top of any higher card.  When being greedy, we place the card on the leftmost possible pile.
2)  If no higher card is showing, thc card starts a new pile to the right of all other piles.

So for this sequence, the piles appears as follows (with the top card bolded for each pile.

7
------
2
7
------
2
7  8
------
1
2
7  8
------
1
2  3
7  8
------
1
2  3
7  8  4
------
1
2  3
7  8  4  10
------
1
2  3       6
7  8  4  10
------
1
2  3       6
7  8  4  10  9
------
1           5
2  3       6
7  8  4  10  9
------

The longest increasing subsequence is equal to the number of piles at the end of patience sorting.  (Exercise, left to reader.) 

The paper then goes on to show other objects that connect to the longest increasing subsequence, including Young tableaux, an interacting particle system on the real line, and determinants of certain matrices.  These connections allow various analyses of longest increasing subsequences on random permutations.

The longest increasing subsequence, by itself, certainly sounds like a nice problem, but when you see these mappings to a variety of different objects, you're overwhelmed by the feeling that there's something fundamental there -- worth learning more about.  And that's what makes the paper such a fun read.

Poll : Conference Acceptances

Consider your favorite conference(s).  Do you think they're accepting too many papers, too few, or just right?  (With SIGCOMM decisions out, STOC/EC/CCC coming up, etc., it seems like a timely question to ask.)  Keep in mind if you think conferences should be accepting more papers, it means longer conferences or more parallel sessions.  When thinking about adding papers, there are different levels you could imagine -- 10% bigger, or 50% bigger.

I'm sure with the SIGCOMM acceptances/rejections out some people think that SIGCOMM could accept more papers.  (33 were accepted;  there was a nominal target of around 36.)  I'm sure some other people like the bar to be kept high.  Increasing paper acceptances by about 10% would get us to the nominal target, a minimal change.  Increasing paper acceptances by about 50% might change the nature of the conference non-trivially, but I'm sure there are arguments on both sides about whether that would be a good or bad thing.  45-50 papers is still not a huge conference. 

Since we're talking across multiple conferences, rather than do a blog poll, please comment in the comments.

SIGCOMM PC, Not Liveblogging

I am absolutely, positively, not liveblogging from the SIGCOMM PC, as that is, I am rightly told, a bad idea.  But these are my impressions after the fact.  (I'm told notifications have gone out.)

This was a big PC -- 50 people.  They did get a great space for the meeting that worked very well -- it didn't seem crowded, we could actually hear each other, etc.  It did seem like  a very large PC -- at the PC meeting, if I've calculated right, each PC member would have on average 7-8 papers to discuss, which seems low for spending a day-plus at a PC meeting.  I think the chairs wanted 50 in order to get a wider range of expertise on the PC.  (External PC reviewers are very rare, as compared to theory conferences.)  On the plus-side, it's an interesting meeting, and I enjoyed listening the the various discussions.  (And, of course, I got some other work done in the times my papers weren't being discussed.)  50 PC members, however, just seems too big.  I would suggest that 40 would have left the workload manageable, still left the committee with enough expertise, and made the PC more interesting for everyone there. 

I'm afraid to say that, unsurprisingly, as a PC we were moving far too slowly, and were, I think, far too negative.  First day, by dinner time, we still had over a dozen papers to discuss -- and all decisions up to that point were supposed to be considered tentative, to be finalized in day 2, which meant plenty more discussion if there was time.  Also, at the end of the first day, had fewer than 20 papers in the Accept/Accept If Room categories (albeit several were in the "Tabled" category, which generally meant more PC members were looking at it or the reviewers were discussing some finer points);  we could, ostensibly, accept about 36 papers.

Matt Welsh wrote an excellent and humorous post on the Psychology of Program Committees, which to some extent applies.  Overall, though, I'm not clear what the problem is.  I think the PC is quite negative;  on the other hand, as I've mentioned, I also think the papers I had to review were pretty bad, so I guess I'm part of the problem.  In terms of timing, though, I think I'm part of the solution -- as was Matt Welsh.  (Early on, asked about a paper that had already been summarized, Matt briefly said, "I liked it.  It's not perfect, but it's very good, everyone rated it high, let's accept."  And we quickly moved on...)

I wonder if there needs to be an attitude change for SIGCOMM (and related) PCs -- a thought that I know has been expressed before.  Papers on the borderline tend to get killed.  There were certainly a couple of papers I would have pushed for that I thought would be reasonable accepts, but was conflicted out of engaging in discussions.  (Perhaps that's why I liked them, and one can interpret individually whether you think that means strong conflict rules are a good or bad idea.)  I'm not sure if starting a meeting by saying, "We're GOING to accept X papers, so find the best ones!" is a possible approach, or even a good idea.  But maybe it's worth trying.    

Tuesday we started early and tried to speed up to get through everything.  Overall I think we did a better job Tuesday, generally moving faster with fewer slowdowns, and we were up against a deadline as people had planes to catch.  I've said before that, overall, I like the conflict rules used by the SIGCOMM PC.  That being said, with time running out, I think a more flexible approach that doesn't require people to physically leave the room should be acceptable (as I've also said in the past, for theory conferences).  I certainly think it's very desirable that conflicts leave the room, but it does take time, and that has to be traded off against other concerns.

In the end, after various reconsiderations and re-animations (some papers, indeed, seem to rise from the dead), we accepted 33 papers;  announcements should now be out to authors, even though the PC still gets some time to finalize reviews.  We finished right on schedule.  

     

The Computer Science Ecosystem

Inspired a bit by some inspirational, high-level talks I've seen the last few days (see Matt's take on Ed Lazowska's talk at Harvard here), I've been thinking about what I'll call the computer science ecosystem.  The inspirational talks often refer a lot to the grand sweeping visions -- science will all be done on the cloud, computerized automobile systems will make driving safer and more efficient, etc.  These generally sound amazing, although to some they can also sound a bit out there.  (Robobees and Sean Hannity, anyone?) On the other hand, there's a lot of basic work down in the trenches creating the building blocks that eventually make the sweeping visions possible.  While some of that work is explicitly done as part of these bigger projects, a lot of scientists are working on their own little pieces of the puzzle without specific regard to the big picture.  And a lot of good work gets done that way too.

So what is the right sort of "research ecosystem" we should have, that balances between BIG and small projects, between individual researchers pursuing their goals and larger groups, between researchers focused on "core areas and problems" and researchers focused on interdisciplinary problems?  How do we promote and build such an ecosystem that lets the various types of research flourish, hopefully in ways that the sum is greater than the parts?

I don't pretend that I have the answers to these important questions.  They're certainly thought about over at the NSF, which decides how much money to distribute among small, medium, and large proposals, and how much to give to different programs, some of which specifically aim to promote interdisciplinary research.  And discussions about these questions have been (and I assume still are) a significant issue for the ACM-SIGACT Committee for the Advancement of Theoretical Computer Science, which gives feedback to the NSF on such matters.

Certainly a concern that always springs to mind is that the funding model for CS will come to be dominated by big projects, leaving little room for the individual researcher or even small groups more common in theory.  But in terms of increasing the funding pie overall for CS, the big project ideas are often much more persuasive, which seems to be the push taken by the Computing Community Consortium.  I don't know currently what the dollar spend looks like from NSF or the other funding agencies;  right now it still feels to me that we have a suitably diverse research ecosystem, but perhaps my view is limited.  

Should There Be a "PostDoc Registration" Rate?

Most every computer science conference has (at least) two rates for registration:  students and other.  Ostensibly, this is because we want to encourage student attendance at conferences.  While it's not often put in these terms, it should be said that this is part of the reason registration fees seem so high:  non-students are effectively subsidizing students.  (Which, I think, is fine.)

What about post-docs?  I've had this question in the past when I was running local arrangements for a conference and have unsurprisingly heard it come up again recently. 

I've looked around and, as far as I can tell, separate registration rates for post-docs don't appear common.  I don't think any of the conferences I regularly participate in have them.  If you know of conferences that do, please comment. 

Since CS seems increasingly to be moving to a state where postdocs will be common -- possibly the norm -- this seems to be a question worth considering.  The problem is there is a big range in postdocs.  We'd like to charge postdocs with money (such as, say, postdocs in research labs that pay for conference travel) the full rate to keep standard registration rates low, but we'd like to charge postdocs that don't have specific travel money less so as to encourage their attendance (and not burden them financially).  While it would be nice to have two different postdoc rates -- postdocs with money and postdocs without -- I don't think that would go over well with conference organizers or the people who could pay for postdocs. 

The default we seem to have wandered into is that postdocs are charged the full rate, but I'm unconvinced that the system ended up that way because of careful thought.  Perhaps it is because until recently postdocs have been relatively rare.  It seems a question worth revisiting.  Any opinions? 

Conference Registration Deadlines (and Fees)

I'm spending the morning registering for conferences.  STOC early deadline is April 30, ISIT is May 1, and EC is May 6.  I'm sure there are others coming up.  Remember to sign up now!  (Why pay the "late signup" fee of $100 or so?)  And please say hello if I see you at any of these events.  

In terms of pricing, early rates are $400 for EC, $500 for STOC, and $675 for ISIT.  I'll let people argue the relative value one obtains for one's money at the different conferences.  It's worth noting the STOC fee includes the Tutorial Day on Saturday;  tutorials for EC and ISIT are extra. 

Last Day of Class!

Sometimes, I think the students are so excited about the end of classes, they don't realize that it's almost equally exciting for the faculty.  While I enjoy teaching, by the end of the semester, I'm looking forward to the break as much as they are. 

I'm hoping the free time will lead to a small research burst (SODA deadline for inspiration -- plenty of time!) but sadly the end of classes doesn't quite match up to the end of academic responsibilities.  Besides the final exam to prepare (and administer and grade), May appears to be the month for all the end-of-year-items:  oral qualifying exams, Ph.D. defenses, even a faculty retreat day.  (Never mind the usual other business -- a PC meeting, a workshop...)  Summer doesn't really seem to start until June.  But still, the last class is a nice milestone, an achievement I can enjoy as readily as the students who have survived the semester with me.  

Random Links for the Day

FemaleScienceProfessor tells an Evil Reviewer story.

The CRA blog tells us that DARPA is back, in terms of funding university research.  Ed Lazowska has related posts here and here at the CCC blog.

If you think deciding authorship is complicated normally, what about for Polymath projects?

For my last lecture in Algorithms and Data Structures, I try to show something that I, at least, think is amazing:  maximal palindromes can be found in linear time.   (pp. 197-198 of Gusfield's book Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology). 

But this year, I didn't miss enough lectures during the semester.  So I still have one more lecture -- a good excuse to finally add a brief discussion of Bubblesearch (randomized greedy) and maybe also Human-Guided Tabu Search into the class. 

Advisors and Publications

There have been several interesting comments regarding the student/advisor relationship on my previous posts (here, here, and here) on co-authorship.  It's clearly an issue that stirs up strong feelings in many, with several anonymous students (or ex-students) protesting do-nothing advisors who still put their names on the papers, and some anonymous advisors suggesting graduate students underestimate the value they provide. 

I tried to do a little reading on the subject, and found some food for thought on my searches of the web.  (References are very welcome in the comments;  here's one and another and another and another, three articles and a guideline for students, that seem pretty good.)  Most schools seem to have a basic official policy or guidelines in place.  Some examples include this bit from the Harvard medical school, this from Duke, and this from Berkeley.  The best I've found is this statement from Penn, which is amusing first because it seems to blatantly plagiarize directly from the (earlier dated) Berkeley one, but also because it links to the specific policies of individual departments.  Indeed, one issue here is that is clear is that different fields seem to have different interpretations of what constitutes authorship, as well as different protocols for author ordering.  The Berkeley/Penn statement go so far as to say, "In some fields, the Principal Investigator of the lab is first author of all publications."  (Take that, graduate students!)  So perhaps one issue is that computer science, as a relatively new field, hasn't set up its tradition for authorship and author ordering;  as we've discussed, even within computer science, theorists default to alphabetical order while systems defaults to students first/ordered by contribution. 

As far as official policies go, though, in general the authorship bar seems to be set intentionally low -- clearly tilted in the direction of advisors.  While there is often a statement that each author should have contributed intellectually to the work -- which would not include just funding the project -- conception and design of the project is considered sufficient for that.  (This seems to match "the PI rules the lab" mentality of some fields -- you may have done all the work, but the PI has set up the entire framework for what the lab works on, so that counts.)  Similarly, while its generally understood that all authors should be involved in the writing, that can be limited to reviewing (and revising) the work.  (PIs are, after all, too busy writing grant proposals to spend too much time on papers.)  

As for my own opinion, I must admit, I'm on the side of the advisor.  That's not surprising;  after all, I am currently one.  As a graduate student, I may have had my complaints about my advisor, but when I switched sides, I became a lot more understanding and sympathetic.  In my experience, many graduate students do undervalue the contributions of their advisors, and the work they put into the students in general (and specific papers in particular).  I'm not saying there aren't bad advisors out there, and that there aren't cases where advisors put names on papers they shouldn't, but my benefit of the doubt will tend to fall to the advisor.

Also, independent of the underlying ethical questions, my personal take is also that graduate students may not realize the "cost" of having your advisor on the paper is small.  Whether using alphabetical order or by contribution, I think the default assumption is that the student was the "primary" author on a work unless other information is available (even when this assumption is unwarranted, which I think is a non-trivial fraction of the time).  (Others may certainly disagree.)  Here, again, recommendation letters and direct word-of-mouth, as well as longer established histories, are extremely important, moreso in my experience than who has their name on what papers.  

We can, certainly, get back to arguing about what is the "right" answer, where the line should be drawn for an advisor to put their name on the paper.  Or perhaps we should go to the extreme of having (as suggested in the HMS guidelines or the authors' guide for Nature) a small writeup for each paper where a description of each authors' contributions are provided.  (Sarcasm note:  as I'm sure I've previously stated, I would hate such a system.)  More realistically, as these many guidelines all seem to state, authors need to talk about this and set expectations earlier in the process.

Where does this leave the unhappy graduate students?  Ideally, entering graduate students should try to find out potential advisors' authorship policies before signing up -- ask the current students for an off-the-record honest appraisal.  Or, ideally, graduate students should talk to their advisors if they have an issue -- let them know early on if you think you're writing a solo paper.  If you've waited until the paper is being written, and then tell your advisor you don't think they've done enough, I don't think you've set up the situation appropriately.

And what should you do when your advisor says, "No, I'm the PI, my name goes on the paper."?  As a practical matter, keeping in mind the strong advisor-oriented tilt of the authorship policies I've seen, realistically, I'd suggest finding a way to live with that, or find a different advisor who has expectations more in line with your own.

Should Harvard's Intro CS Class Do Away with Grades

There's been discussions of late on the possibility of offering our intro CS class in two flavors -- a "graded" and "SAT/UNSAT" version.  (Same class, just two different grading options formalized into two course numbers.)

I was toying with whether or not to do a post about the issue when fortunately my colleague Matt Welsh wrote a comprehensive post on it at his blog Volatile and Decentralized and saved me the trouble.  So here's the post -- Should Harvard's Intro CS Class Do Away with Grades?

Guest Post : Justin Thaler/New Paper

I'm happy to introduce Justin Thaler, a first-year graduate student at Harvard that I'm advising.  You can find out more about Justin at his home page.  Justin volunteered to write a post about a paper we (Cormode, Mitzenmacher, Thaler) have put on the arxiv.  (I note, in line with current discussions, the author list is in alphabetical order, but as Justin is the student, you can rightfully assume he did most of the work.)  

------------------------------

I'm happy to write a guest post announcing a new paper, "Streaming Graph Computations with a Helpful Advisor (arxiv link)" by me, Michael, and Graham Cormode of AT&T Labs -- Research. In our paper, we consider a variation of the streaming paradigm in which a streaming algorithm is allowed access to a powerful advisor who may annotate the data stream. We're primarily motivated by the emergence of commercial cloud computing services, like Amazon EC2, but we also have in mind other settings in which outsourcing of computation is desirable, such as weak peripheral devices that need to delegate computation they cannot handle on their own.

In many of our motivating applications, the helper is not a trusted entity; the commercial stream processing service may have executed a buggy algorithm, experienced a hardware fault or communication error, or may even be deliberately deceptive. For example, since executing a computation is costly, a cloud computing service may have a financial incentive not to complete the computation they were hired to perform, as long as they can convince their client otherwise. As a result, we would like the helper to prove that she executed the computation correctly, especially if providing the proof is not too costly.

In our paper, we primarily consider problems on graph streams, which are of high interest given the recent explosion in the number and scale of real-world structured data sets including the web, social networks, and other relational data. Many results for graph streams have been negative; apparently most graph algorithms fundamentally require flexibility in the way they query edges, and therefore the combination of adversarial order and limited memory makes many problems intractable in the standard streaming model. Consequently, these problems are ripe for outsourcing.

We prove a host of positive results for many standard graph problems in our model, many of which are optimal or near-optimal. We also provide a protocol achieving optimal tradeoffs between proof-length and working memory for matrix-vector multiplication, which is my personal favorite.

While we're introducing our paper to the blogosphere, it seems worthwhile to mention some other blog posts closely related to our work. Richard Lipton describes work by himself, Atish Das Sarma and Danupon Nanongkai on the Best Order Streaming Model which happens to be a special case of our own
http://rjlipton.wordpress.com/2009/08/24/streaming-models-both-old-and-new/#more-3294.
In a more recent post, Professor Lipton describes a different notion of "security" in Cloud Computing.
http://rjlipton.wordpress.com/2010/04/08/can-we-trust-cloud-computing/#more-4665
The concern there is on keeping the data private, and without explicit streaming constraints, but it's good to see other emphasis on trust within outsourced computations.

Bursts -- a new Barabasi book

At the end of the month, Barabasi's new book, entitled Bursts: The Hidden Pattern Behind Everything We Do, will be released.  Here's the pre-order Amazon link, and he's apparently put a web page up with information about the book.  Barabasi is something of a controversial figure in the networking community, as mentioned previously in this blog here;  for example, there are those that feel he overstates claims without evidence (the power laws on the Internet controversy).  However, his earlier book, Linked: How Everything Is Connected to Everything Else and What It Means, was one of a series of books (including also Watts' Six Degrees: The New Science of Networks) that popularized networks and power laws in the public consciousness a few years ago.  So it will be interesting to see how this book plays out, both in how it does with general audiences, and what scientists think of the content.

I've also still been waiting for the Easley/Kleinberg book Networks, Crowds, and Markets: Reasoning About a Highly Connected World.  It seems to be on pre-order for June.  While this will be a more "academic" book -- it's written as a textbook for an introductory course -- I'm wondering if it will reach the public consciousness.

I've always wondered my more computer scientists don't try to write "popular science" books.  It would seem that we work in an area that should be of more popular interest than physicists, but they seem to write a lot more for widespread public consumption.  It's something I'd like to try -- I started playing with an idea a few years back (after tenure) but the project stalled.  Writing a book like that seems to be a multi-year commitment, and perhaps it's hard in our "get the paper ready for the next deadline" culture.  It certainly was hard for me to keep up momentum, and find the right voice and message.  But perhaps someday.

What's the Co-Author Line?

Continuing the past discussion on authorship issues, I've been considering the questions: at what point has a person involved in the project done so little work that they should not be included as an author?  For today's post, let's not consider the case of advisors, which is arguably a special case that should be considered separately (and we will return to in a further post).

It's interesting that my preferred approach of alphabetical ordering of authors arguably makes this question thornier, since the tendency of alphabetical ordering to equalize the contribution among authors suggest that there should be a contribution threshold below which you should be removed as a co-author.  This is probably still true under other ordering schemes as well, but it seems more striking under alphabetical ordering.

Having thought carefully about it, I've come to a firm conclusion: it seems like a challenging issue with no right answer.  In spirit, I agree with David Eppstein's comment in the previous post:

"The rule I tend to follow is that there are no 1% coauthors. If you haven't contributed an idea that you can point to as part of the paper, or done some of the hard work of turning ideas into proofs, or done some of the implementation or data analysis, you don't get to be a co-author."

In practice, I've found it's a lot fuzzier.  Sometimes the "idea" is the initial formulation of the problem, not the solution.  Should that count as a contributed idea?  Many papers, I find, boil down to one key idea, and the rest is just details.  Four of you spend a bunch of time kicking around ideas that don't work, then one sees the idea that works, and the paper really writes itself from there.  Should the other three not be co-authors?  These aren't hypotheticals.  I've been in situations where I've talked with someone about a problem, which I considered at that point "my" problem, with the idea that we would possibly work together on it, only to have them present me with a finished paper they were submitting on their own a few months later (apparently without realizing that I might be peeved by this).  I've been in a situation where one co-author, after much dead-end work by everyone, came up with the key insight and then thought that the result should be a single-author paper.  I'm sure I (and others) can come up with similarly unclear situations.

I recognize that, in both of these circumstances, one could argue that the other party was in the right.  But it really doesn't matter who was right;  in the end, these became people I would be very wary of working with in the future (and perhaps they felt the same of me).  As we've discussed before, one of the great benefits of collaborating is establishing long-term collaborations over multiple problems.  That didn't happen.  What I've learned was that, in such situations, one should be clear ahead of time what the expectations are.  Being clear when starting a collaboration about expectations might be a little awkward, but seems better than awkwardness later.  If you're telling someone a problem and consider it from that point on a collaboration, tell them.  I personally think the default assumption should be that if you're in the room on multiple occasions when working on a problem, you should be considered a co-author even if you're not the one to make the breakthrough, but if there's a reason that shouldn't be the case, somebody should speak up sooner rather than later.  Different people may use different rules or guidelines for what they consider sufficient for co-authorship on a paper, and setting expectations is really the key.

As another story, I should admit I have been involved in a paper where I was a 1% contributor.  I started working with a group on a problem, but it was a group in a distant location, and while I was there -- for a short period -- no progress was made.  The group, with much more work, eventually solved the problem.  I was asked by the senior author whether I wanted to be on the paper, and I declined.  I thought a potentially awkward situation was handled perfectly by this senior author.  They were up front that, as it turned out, I hadn't contributed tangibly to the paper, but were willing to accept that, in this case, it was an accident of circumstance rather than intent.  I was glad they respected me enough to discuss it openly and leave it as my decision, even though in my mind the proper course was clear.  (Indeed, in this case, I thought it was so clear I would not have been surprised or offended if they hadn't offered.)  I assume that if I had decided otherwise I would have been a co-author on the paper without argument, and they would then have to consider that history in future dealings with me.  I also think that, if I had said I wanted to be a co-author on the paper, it would have been appropriate for them to add me, because perhaps we had had different perceptions and expectations regarding the work.

In any case, I think the issue is a difficult one, made even more so because it's tied to quite directly to one's job performance, which tends to color self-perception.  Perhaps others can add more clarity to the question in the comments.  

Crimson Article on Women in Computer Science

From a few days ago:

Computer Science at Harvard Sees Large Gender Imbalance

It's listed as a news article, although I don't think this is news.  It is something we are trying to figure out, and do better:

“It’s something that we talk about a lot,” said Associate Dean for Computer Science and Engineering J. Gregory Morrisett. “We are coordinating with a bunch of departments around the world and are trying a lot of different things in the hopes that we will uncover some of the issues and correct for them.”

More on Authorship

My last post, on what I called "60-40" papers, where one author does non-trivially more of the work than the other(s), seems to have generated some interesting comments, worth following up on.  There seem to be multiple issues in the comments that, to me, appear essentially orthogonal:

1)  How does the community properly assign credit for 60-40 papers?  Should we use author ordering or some other mechanism to assign credit?
2)  What about advisors who do minimal to zero work but put their name on the paper?
3)  At what point has a person involved in the project done so little work that they should not be included as an author (by either withdrawing willingly, or possibly by being told "you're not an author").  (I think of this as separate from the "advisor" issue.)

Let me start with item 1, assigning credit.  I promoted the approach used in theory (derived, apparently, from mathematics) of alphabetical order, claiming credit comes out through things like letters and who gives the talk, and is determined more clearly over the course of a career.  Many question this;  indeed, many other fields use entirely different systems.  Many fields use author order to signal the level of contribution in some way, so that being "first author" has significant meaning.  At the extreme, the journal Nature, for example, suggests that author contributions should be fully specified in each article in their guide to authors:

"Author Contributions: authors are required to include a statement to specify the contributions of each co-author. The statement can be up to several sentences long, describing the tasks of individual authors referred to by their initials."

Graduate student and postdocs, in particular, are more concerned with systems that clarify credit, and this is understandable.  They have short career track records, and want a job;  making sure that they get their proper credit often seems, to them, quite imperative.

I'd like to defend the alphabetical, no-explicit-credit-assigned system, and then provide a couple of stories.  (If you find that indulgent, you can skip the stories.) 

One philosophical approach is to try to start from a blank slate.  Forget about your current situation, and how your field does things.  Your starting point is that you're just starting a career in science.  What sort of system do you want to use?  I'd argue you'd want to use a system that would lead to long-lasting, productive collaborations;  that would have minimal overhead;  and that would still provide meaningful ways of calibrating people over appropriate time periods.  I think pure alphabetical does that.  It removes the need to fight over (or even discuss) who contributed exactly what, leading more easily to frequent and repeated collaboration.  To be clear, I have a strong bias:  collaborations, I think, are great for scientific production, and on the whole make research much more fun.  Alphabetical order is clearly easy.  And while it's weak on allowing someone to find out how much each individual author contributed to a specific multi-author paper, over the course of several papers, I think the calibration works, especially when augmented with additional information such as letters in job searches and promotion cases.  Further, it's not clear that other systems are really stronger in terms of assigning credit.  Authors can disagree on contributions -- how does this get settled, and what does it do to future collaborations;  in multi-author situations where order ostensibly matters many advisors will game the system, for example by putting students first regardless of their contribution in order to prep them for the job market or out of professional courtesy;  and it's not clear how, for example, to value different types of contributions, like ideas vs. data collection and analysis.  My bias is that the blank slate scientist starting their career would pick the alphabetical order system.

I have at least one data point for this conclusion: myself.  (Here's where the stories start.)  In graduate school, a bunch of us students got together and wrote a paper.  This was a case where I was definitely the 60 author, and I thought it would be best if I was first author.  The other students didn't object, but since I knew it wasn't standard for theory, I asked my advisor.  (He wasn't a co-author for this paper, so his view was not biased in that regard.)  He told me it was my choice, but that I needed to recognize the following:  I would possibly get more credit for this paper, but, from then on, I would have adopted a system where, for every paper, I'd have to face the possibility of constructing the author order with my co-authors.  Did I want to have that discussion for every paper down the line?  I went with alphabetical order and have never looked back.  I always recommend alphabetical order, although when I work with people in other areas I do defer to whatever system they want to use, and tell them they can put me wherever they like in the ordering.  (It is true that, with tenure, one can care much, much less about such things.) 

On the other side, another story.  When I applied for my CAREER grant, apparently I was on the borderline, and it took quite some time to get the final word.  I asked the NSF officer for feedback -- especially in case I needed to resubmit.  (Apparently, enough money came through in the end to fund me.)  One thing he said was that a lot of my work had been co-authored with very talented people, and it wasn't clear what my contributions were.  This was a case where, obviously, there were no recommendation letters to draw from.  Still, I was offended then by the comment, and looking back I still find it ridiculous.  At that point, I'd written multiple papers with these other authors (who were not my advisor) -- clearly they thought I was contributing something worthwhile.  And why was the assumption that they were the 60 contributor, instead of me?  It's not clear that using author ordering would have helped in this case, or that such cases are at all frequent.  But it does help me understand alternative points of view on the underlying question.

60-40 papers

A recent paper I worked on was a 60-40 paper.  That's what I call it when one of the authors does noticeably more of the work.  Really, it could be a 70-30 paper, or some other division; or with multiple authors, it could be a 50-30-20 paper.  But I use the phrase 60-40 paper to refer to all of these situations.  In this case, I was the 40.

60-40 papers aren't at all abnormal, and I've done enough papers not to let it bother me.  When I'm the "40" author, I usually try whenever possible to do what I can to help even things out, for example in the writing/editing/revising stages;  when I'm the "60" author, I recognize that the other authors have contributed, and the paper wouldn't be what it is without them.  I've had amusing discussions with one co-author where we ended up admitting we both thought we were the "40" author for the paper we were writing.  That was a collaboration that lasted for several papers;  apparently, we both thought we were getting a good deal.  I don't think I've been in many collaborations where multiple authors thought they were the "60", but my guess is those could be problematic. 

Fan Chung has a nice page up with advice for graduate students that I think puts the 60-40 issue in perspective.   At the end, under research collaboration:

What about the division of credit?
-- In math, we use the Hardy-Littlewood rule. That is, authors are alphabetically ordered and everyone gets an equal share of credit.
--  The one who has worked the most has learned the most and is therefore in the best position to write more papers on the topic.
--  If you have any bad feeling about sharing the work or the credit, don't collaborate. In mathematics, it is quite okay to do your research independently. (Unlike other areas, you are not obliged to include the person who fund your research.) If the collaboration already has started, the Hardy-Littlewood rule says that it stays a joint work even if the contribution is not of the same proportion. You have a choice of not to collaborate the next time. (If you have many ideas, one paper doesn't matter. If you don't have many ideas, then it really doesn't matter.) You might miss the opportunity for collaboration which can enhance your research and enrich your life. Such opportunity is actually not so easy to cultivate but worth all the efforts involved.

I'd just add a bit to this.  Usually the "60" author will, actually, get more credit in various ways:  usually they're the one to give the talk on the paper, for example.  (It can also come out in letters when really needed.) And it's not so clear that a string of 60-40 collaborations with one author repeatedly being the 60 is so bad;  without the 40, the research or the paper might not ever get done!  Good collaborations are indeed enriching.  To some, particularly graduate students, this approach and attitude might seem strange, but I recommend considering Fan's suggested understanding of collaboration.

To all the co-authors out there who have been the 60 to my 40, I appreciate your putting up with me.  And to all the co-authors who have been the 40 to my 60, as long as we had a good time working on the paper, no worries, and thanks!