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!    

Sexual Harassment Policies (Yale v. Harvard)

My brother, in what I assume is a blatant attempt to be mentioned in this blog (Hi Steve!!!), sent me a link to the following article about a new rule (or, as the article describes it, "A Sad Day") at Yale, banning professors from having sex with undergraduates in all circumstances (not just students that, say, are in their classes).  More details at for example the Yale Alumni Magazine.    

I was all ready to start looking down my nose at the competition for being slow to adopt what are in my mind obvious rules to have, but decided to check Harvard's policy first.  (Always a good idea.)  Harvard's policy, arguably, isn't even as strong as Yale's old policy.  (Harry Lewis will, I imagine, correct me if I am mistaken in my interpretations or usage of documents.)  The relevant information seems to be here.  The policy description includes the following, under the heading UNPROFESSIONAL CONDUCT IN RELATIONSHIPS BETWEEN INDIVIDUALS OF DIFFERENT UNIVERSITY STATUS:

"Officers and other members of the teaching staff should be aware that any romantic involvement with their students makes them liable for formal action against them."

This seems to suggest that faculty can't have "romantic involvement" with their students, but some old letter to the Crimson suggests that the wording is much weaker than that (the article is here, the letter is here).  Strictly speaking (according to the letter), the wording seems to suggest that faculty members involved with students face the risk of a the student filing a sexual harassment/unprofessional conduct complaint;  but if the relationship is brought to light by a third party, there's no (apparent) cause for disciplinary action.  IANAL, but this seems like a possible interpretation;  I'm not sure what the current interpretation is here at Harvard.  

Indeed, later on the policy states:

"Amorous relationships between members of the Faculty and students that occur outside the instructional context can also lead to difficulties."

The rest of the paragraph suggests potential problems if Faculty engage in "romantic involvement" with students who they are not directly teaching, but seems to make clear (by my reading) it's not forbidden in any sense.

I've certainly heard arguments in the past that such rules shouldn't exist.  I can even see that there are potentially complicated lines -- should a professor in the Faculty of Arts and Sciences not be allowed to date a Harvard Law student?  (Extra credit:  why or why not?)  But given the potential for abuse (both intentional and unintentional) of the power relationship, I'm unapologetically on the "no faculty - undergraduate romance" side.  Or, as it says in the Yale Alumni Magazine:

'An imbalance of power forms the rationale for treating Yale College students differently from their older counterparts. Undergrads, the revised handbook says, “are particularly vulnerable to the unequal institutional power inherent in the teacher-student relationship and the potential for coercion, because of their age and relative lack of maturity.” '

Duh.  Good for Yale.

NSF Review Issues

My understanding is that the turnaround time on NSF decisions should be approximately 6 months.  (See, for instance, their own diagram of the review process.)  So I admit to getting a bit edgy after month 7 has come and gone without hearing anything on a proposal I have in.  I went back at looked at my NSF proposal history, and found a small bright side:  proposals that were accepted seemed to take a longer time for the decision feedback to arrive.  Sadly, this rule did not seem to be universal, and my personal sample size is too small for rigorous conclusions.  Feel free to share your own anecdotal evidence.  Meanwhile, I'll try my best to forget about it until we get to month 8.  

Also, this year, I have been asked (more than once) to review a single proposal "off-panel" (that is, I didn't serve on the panel that the proposal was part of).  I can't recall having been asked to do this before, and wonder if there's a policy change behind it or if it's business-as-usual and I'm only now noticing it.  I certainly don't mind -- I'm more than happy to help the NSF, and even more happy if I can do so without having to travel to DC.  On the other hand, I worry that this approach might cause the same sort of problems that can occur with subreviewers, such as consistency across reviews.  

Energy Sustainability

I spent an entertaining hour this afternoon listening to David MacKay of Cambridge (UK) give a talk about the Future of Energy here at Harvard.  I've mentioned David in this blog before.  He did a lot of early work on low density parity check codes and deletion codes, so we've run in the same circles for quite some time.  But now, besides his well-known book on information theory (Amazon link, free downloadable version), he's written a book on sustainable energy (Sustainable Energy - Without the Hot Air : Amazon Link, free downloadable version) that was the subject of his talk.  David's also recently been named Chief Scientific Advisor to the Department of Energy and Climate Change (UK). 

The talk was based on the book.  David's starting point is the question, "What would we have to do to move to a world where we weren't using fossil fuels?"  (The "we" he's talking about is usually the UK, but it applies elsewhere as well.)  He then takes a truly scientific approach.  He considers various possible renewable energy sources (wind, solar, biomass, tides), and estimates things like their energy output per unit area.   Based on these calculations, he figures out how much land would be required.  So, for instance, if you were willing to cover 1/2 of Britain with windmills, things might look OK, but that's not a very likely possibility.  He also considers the demand side of the equation, and what might feasibly be done there.

The book (and the talk) are not overtly political.  Whether you believe in global warming or not, the question of sustainable energy is important -- for national security concerns, you might not want to be dependent on getting your energy from, for example, oil-rich countries.  His book is not about the politics;  rather, he tackles these questions as a scientist, producing the numbers that are needed for intelligent, reasoned discussion and debate on the issues.  That might sound dry and, possibly, boring, but not in David's hands.  He's blessed with a fine wit and a charming style that comes out in the book and even more so when he's speaking.  (His slide showing a collage of posters from places protesting the introduction of windmills into their community, for instance, received a lot of laughs.) 

David has done a truly rare thing as a scientist, writing a book firmly about the science of an issue of current import that people are actually reading and that is raising the level of debate.  I admire his courage in taking on a challenging assignment, and hope his work helps lead to the positive changes he is looking for.    

Two Inspiring Posts

UPDATE:  Make that three!

Inspiring me to blog, that is....

Matt blogs about the psychology of program committees.  It's one of those things that would be funny except that it's true.  So true.  So, so true...

One of the commenters raises an interesting option.  Every PC member gets one "trump card" to decide to accept a paper unilaterally.  (I suppose one could also allow a trump card to be used to reject a paper unilaterally.  But then what happens if two people play opposing trump cards?)  What do you think?  I like the idea in principle -- if a PC member has such a strong opinion on the paper, it should be accepted -- but I think in practice it's an idea rife with complications.  Gamesmanship in the committee about when/how to use the trump card and potential abuses from conflicts of interest come to mind.  Might you be inclined to use a trump card rather than "go to waste", even if you didn't feel quite so passionately about a paper?  I think if everyone used it in the manner it was intended, it could be a great idea.  On the other hand, if PCs were perfect, we wouldn't have posts like Matt's (and might not need the trump idea in the first place).

Lance complains about traveling too much.  Some academics I know would laugh at the idea that hitting 50K miles gets you anywhere close to being a too-frequent traveler, but (like Lance) that's pretty much my threshold too -- it's roughly a flight across the country or to Europe each month.  Add in some other shorter travel, and it really does up.

At this point, I avoid trips that keep me away overnight if at all possible.  I've turned down a few colloquium talks this year because of this problem.  If we can work out a travel schedule based on my taking an early flight from Boston and a late flight back the same day, I'll definitely try to make it work.  The kids/family can manage school/dinner without me for a day.  (There's also my class to consider, of course, during the semester, but let's temporarily leave that aside.)  I'll take a late flight out the night before sometimes if needed.  But if I have to miss two dinners (or two morning walks to school) it's much, much less likely I'll do the travel.  It just adds up quickly to too much time away.  (Usually the way flights work out you're stuck leaving early the afternoon before, killing the day, or getting back mid-afternoon on the way back, killing the day.  2 days is a lot of time to devote for giving a talk.  And if I'm missing two days in a row, I'm definitely missing a class during the semester...)

Conferences obviously are different -- but it's rare I go to a conference where I don't have a paper, for essentially the same reason.  I do try to arrange longer trips, where I can bring the family -- I arrange a 1-2 week west coast Bay Area tour most every summer and try to give talks at all the major places I can manage -- but it's a difficult balancing act.  I suppose I'll want to travel more again once the kids grow up and leave the house.  I hope I'll still have work worth traveling to talk about then!

A third inspiring post by way of Muthu.  Tim Roughgarden has won the Grace Murray Hopper Award, and Bellare and Rogaway have won the Paris Kanellakis Theory and Practice Award.  Congratulations all around!

     

Reading a Research Paper

In the category of "waste nothing", here's a handout I wrote way back when (over a decade ago) that I use for my standard graduate seminar class on How to Read a Research Paper.  Others have found it useful enough to use it (with permission) rather than construct their own.  If you like it, feel free to use it, and modify it as you like.  I even have the Latex around;  just ping me if you want it. 

There are other pages and places with more advice on the topic, so you might want to look around.  Searching on phrases like How to Read a Research Paper (and other variants, like How to Read a Technical Paper) will yield plenty of pages.  I like the "What to Read" section at the bottom of this page from Jason Eisner -- creative Web search and forward/backtracking references are, I think, often underappreciated skills.

Google-Viacom Documents

I don't blog about my work as an expert witness, but for those who are interested in such things, since I (currently) have nothing to do with the case, I can happily point you to the court documents now out in public for the Google-Viacom case.  You can find pointers to them here.  Both sides are moving for summary judgment;  if you haven't heard of that before, Wikipedia describes it.  I haven't read them over yet, so I don't have any opinion to offer.   

More on SIGCOMM

The first round of SIGCOMM is pretty much done.  (As usual, many reviews are still out, though the deadline has passed.)  I had mentioned earlier that my first round papers, in general, seemed pretty terrible.  My colleagues agreed.  This year the ratings scale was 1-10 (which I dislike over the standard 5 point scale from previous years), and I had five papers that didn't get a score higher than a 3.  (A score of 3 is "Reject";  scores of 1 and 2 are below reject.  A score of 5 is still only a borderline reject, for comparison.)  In some cases, I gave a 3 and was the high score.  I did (eventually) read a couple of good papers that may well be accepted.  Hopefully, I'll see better papers in round 2.  

Matt Welsh, perhaps at least partially inspired by being on the SIGCOMM PC as well, has suggested an approach for dealing with the large quantity of awful submissions by charging authors to submit;  Suresh disagrees.

Interestingly, the scores (and reviews) on my papers were generally consistent across the line, with a rare exception or two.  Since there's always some overenthusiastic anonymous commenter who thinks its important to call SIGCOMM an insider's club whenever I blog about it, I'll repeat that I'm not aware of belonging to any such club, and once again, the reviews I see from others not only make sense, they match my own opinions, which I view as independent, to a striking degree.

Kindle Textbooks

I've had a couple of people point out to me that Probability and Computing: Randomized Algorithms and Probabilistic Analysis (my book) is now available on Kindle.  I looked around and saw that several other standard texts are now available that way as well:  Algorithm Design, Algorithms, Approximation Algorithms, Computational Complexity: A Modern Approach, and Introduction to the Theory of Computation.  (Even the omnibus The Princeton Companion to Mathematics is available on Kindle.)  Strangely, several other texts apparently aren't:  Introduction to Algorithms, Third Edition, Randomized Algorithms, Algorithmic Game Theory, and Concentration of Measure for the Analysis of Randomized Algorithms.  While I can understand that older texts might not be easily moved to a Kindle format, the Concentration of Measure book is new, so I'm not sure what it is that is separating Kindle-ized books from unKindled peers.  Anyone out there have any insights?

I suppose I'll see in my next book sales statement if any Kindle copies were sold.  In general, the Kindle version seem to go for just a few dollars less;  Algorithm Design is a big exception, with the Kindle edition going for over $25. less than the hardback counterpart.  Sometimes, it looks like you can buy new copies of the book less than the Kindle price (usually from Amazon third party dealers).  I don't own a Kindle (yet), and I wonder how they would be for textbooks.  The textbooks I've listed above I'm happy to have on my shelves for reference.  I suppose if I had them in a universal, pdf-like format that I could access and make use of essentially anywhere, I'd be happy with that too.  Particularly if I had capabilities like search available.  But I wouldn't want my copies of the book tied to a particular piece of hardware.  If I lose my Kindle, do I lose my books?  That's fine for disposable books -- and probably for many students many textbooks fall into that category.  (Use them for a semester, then forget about them.)  It wouldn't be fine for me for these books.

Can anyone comment on the Kindle textbook experience?  I'm interested generally, and in the particular issue of the "permanence" of books that might be references one wants to keep.  Someday soon, I'll be getting one of these (or another e-reader), and it would be useful to know whether it's currently worth moving to a system where I try to keep important texts in an electronic, rather than paper, format.        

And More Fun News....

Right after Stuart Shieber sent me news on CS undergrad earnings, Harry Lewis sent me two additional links.  The first is a nice Boston Globe piece on the increase on undergraduate majors in the sciences at Harvard.  

The second is much more amusing.  Apparently, the Harvard Robobees project has made #1 (that's right, we're number 1!) on Sean Hannity's list of the 102 worst ways the government is spending your tax dollars.  Now, I try to stay apolitical on this blog, but I have to say, I'm impressed by Sean Hannity's lack (well, actually, more like a complete absence) of acumen in understanding the nature of scientific research.  A look at the Robobees home page, I would think, would certainly suggest that there's important scientific and engineering questions underlying the long-term challenge of building a robotic bee.  Of course, maybe the Hannity camp just objects to the government spending money on science generally, I don't know.  I'll go on record as suggesting that nobody from the Hannity camp bothered to look at the Robobee home page.      

Good News for Computer Science Majors

Undergraduate computer science majors, according to the National Association of Colleges and Employers, are still getting paid well.  If you don't want to be an engineer for an oil or chemical products company, we're still apparently the best way to go.  (I'd like to think careers in CS are more interesting than in these areas as well, but I really don't have the experience to say.)

Thanks to Stuart Shieber for the link. 

A Conflict Question

I was recently asked the following question:

Suppose you're the PC chair, and someone who has submitted a paper asks you NOT to have the paper reviewed by a specific person on the PC. Do you honor that request?

It's an interesting question -- that I hope others will comment on -- though as a default my answer would be yes.  I certainly have had run-ins of sufficient severity with various people through the years that I would not want (and would likely ask) for them not to review my papers if the issue came up.  Looking at it from the other end, if I am on a PC and those people submit a paper, I make sure not to review them.  (Usually it is sufficient simply to rank them low on my list of desired papers, but I have also told PC chairs in advance I would not review certain papers if they seemed likely to head my way.)  It is not that I actually think I couldn't give a fair review;  it's that I think it's inappropriate, in such a situation, for me to give a review in the first place.  If as a PC member I have the right (actually, I would say, a responsibility) to refuse to review a paper under such circumstances, it seems fair that a submitter can ask for a specific PC member to not review a paper as well.

Context does matter, though.  In the networking conferences I have served on, this is standard -- PC members and submitters are expected to list their conflicts.  Indeed, one issue that seems to have arisen lately is that there is suspicion that some people submitting papers are abusing this right, listing people as conflicts when they are not because they are known to be "challenging" reviewers.  While I'm skeptical this sort of gamesmanship gains anything (challenging reviewers are usually calibrated appropriately at the PC meeting), it is a concern that once you open the door to such requests, you may need to make sure the privilege isn't abused.

For theory conferences, where many people seem painfully unclear on what "conflict of interest" even means, I'd grant such a request as a matter of course.  

Congratulations to Chuck Thacker

The news has hit the wires -- Chuck Thacker is this year's Turing Award winner.

I had the great pleasure of getting to know Chuck while I worked at DEC SRC.  He's a character, a tinkerer, and a great and curious mind.  I think recognizing his work -- the Alto -- is a great choice.

 

EC Papers Up

The list of accepted papers for EC is up.  I'm happy to say that our Swoopo paper made the list.

I was surprised in the acceptance letter to find that there were 45 acceptances out of 136 papers -- an acceptance rate of about 1/3.  (Compare with WSDM.)  This makes it one of the less "competitive" CS conferences I know of, although a little research shows this is a bit unusual -- last year the numbers were 40/160 or so, so they accepted more papers and had fewer submissions this year.  Is that a trend in the making or an accident of timing this year?  Also, while I'm an EC newbie, the list of papers looks very interesting, with plenty of top-tier names.  "Competitive" or not, I'm expecting high quality.  I'm really looking forward to it -- and not just because its location makes it remarkably convenient for those of us in the greater Boston area.      

Carousel (NSDI Paper)

The "final version" for our NSDI paper, Carousel: Scalable Logging for Intrusion Prevention Systems, is now up.

Here's the main idea.  In IPS systems, the logger can get overwhelmed during an attack.  Bad sources (with other related info) need to be recorded for later examination, but there's only a small amount of on chip memory to buffer bad sources, and only a small about of bandwidth (compared to the rate data is coming into the system) from the memory to the more robust recording infrastructure.  How do you get all, or almost all, of the sources?

In our model, bad sources are hitting the system repeatedly -- the denial of service attack setting.  On the plus side, this means you don't have to log a bad source the first time it appears - the assumption is it will come back again.  On the negative side, you want to avoid sending the same source to the recorder multiple times, as it wastes your small bandwidth.  (Dups can be removed at the recording side, though.)

The baseline solution is to just grab a bad source to record for the buffer as soon as you have room after you send one out.  We consider a random model -- there's a bunch of bad sources, and the next one to appear is random from that set -- that shows that this approach is bad;  by connecting it to the coupon collector's problem, we show it can be a logarithmic factor off of optimal.  Other experiments show it can be even worse than this in realistic situations. 

Our solution has two parts.  We hash-and-partition the bad sources, adaptively finding a partition size that so that the bad sources in each partition fit into our small memory.  That is, we hash each source, and put in a partition according to the last k bits.  This breaks our N bad sources into groups of size (roughly) N/2^k, and if N/2^k is small enough so that the partition fits into memory, then (assuming we can avoid duplicates), we no longer have a memory problem.  We just run through all the partitions, giving us our "Carousel".   

To deal with duplicates, we do the obvious -- we use a Bloom filter (or equivalent structure) to avoid sending duplicates within each partition.

This hash-and-partition plus Bloom filter type framework seems like a potential generally useful trick;  more details -- including both theoretical analysis and experiments -- are in the paper.

An interesting thing came up in the reviews.  We pointed out that the "straw man" approach -- do nothing -- was quite bad.  We mentioned that just using a Bloom filter -- without partitioning -- wouldn't really help, but then ignored that option.  Apparently, this was a big concern for the reviewers;  my understanding is that it almost "sunk" the paper.  They wanted to see more details, including simulations, on this option.  Luckily, it was still accepted, and in the final version, in response to the reviews, we've added some theory and simulations to prove our point.  (The point is you'd need a really, really big Bloom filter -- too big for your memory -- to track all the sources, so eventually you have to clear the Bloom filter, which causes you to lose whatever it was going to gain you in the first place.)  I'm not sure what the takeaway is there.  The right outcome happened -- they should have accepted the paper, and we could add the appropriate stuff.  But I'd have hated for what in my mind is a minor issue to have killed the paper.  Perhaps we should have said more about it, although at some point space prevents you from providing details on every possible variation you could consider (even if you have actually considered them).    

This seems like a good place to remind people about this book -- Algorithms for Next Generation Networks -- which includes a survey about these sorts of hashing applications in networks by Adam Kirsch, George Varghese, and me.  The book does seem a little pricey;  we have a slightly older version of the survey available online.   

   

SIGCOMM papers

A commenter asked me a while back to say what I thought of the SIGCOMM submissions this year.

I'm finally getting around to reading and reviewing. (First round reviews aren't due for at least a week!) And so far, by and large, the papers I'm getting are pretty terrible.

This generally seems to happen to me on the first round, but this year is extreme. My first several papers just don't belong at this conference. (Arguably, they don't belong at any conference...) There's some number of papers submitted at every conference that are just not serious submissions, and apparently I got more than my fair share on the first round.

This makes it harder to judge the other papers -- it's hard to calibrate when you start with a lot of junk. Many of my other papers are theoretically oriented, and I'm not too optimistic about them. There's room for theory papers at SIGCOMM, but I think the bar is, rightly, pretty high. When I read a theoretical paper for SIGCOMM, I look for one of two things. First, it could be the paper has a nice theoretical idea that's actually useful. The problem there is that it's incumbent on the paper to clearly demonstrate the utility, and most fall down in that regard. I quote the SIGCOMM call: "SIGCOMM is a highly selective conference where full papers typically report novel results firmly substantiated by experimentation, simulation, or analysis." A mathematical analysis alone generally does not count as a firm substantiation. [Such papers generally have a better chance at INFOCOM -- which I think is a good, and very important, thing! There needs to be an outlet for more theoretical networking work, and perhaps it's just better suited for a big conference. Many such papers will end up having minimal impact, but once in a while, a good idea gets built on and has a real impact.]

Second, it could be the paper really challenges our way of thinking, introducing a new framework that seems a clearly important guide for future work. Such papers are rare, but important. I seem to have a number of economics-networking papers that are very high-level, and I'm really trying to understand if any of them have that character. Again, because SIGCOMM is so selective, I think the bar is very high for such papers. I'm really looking for something that enhances our fundamental understanding of the network.

That's it for now. If you have a submission, don't let my comments make you antsy -- the meeting is still a long way away, and I'm quite sure I'm not reading your paper anyway.

Congratulations to David Johnson, Knuth Prize Winner

I'm pleased to hear that David Johnson has won the Knuth Prize for "his contributions to theoretical and experimental analysis of algorithms."  David has done a great many wonderful things, but I thought I'd highlight something that I imagine is underappreciated today, his book Computers and Intractability: A Guide to the Theory of NP-Completeness.  We're a bit spoiled these days, what with Wikipedia pages with lists of NP-complete problems and online compendiums with references.  But in ye olden days, when I was a grad student, if you had a reduction you needed to ponder, you went to Garey and Johnson.  The book was an inspiration, and an invaluable research resource, to many.  It's one of the most cited (the most cited?) references in computer science, and the book will rightly hold a special place in the history of computer science. 

Teaching Bloom Filters

As I finished my lecture today for my undergraduate algorithms and data structures course, after spending about half an hour explaining Bloom filters and what they did, I couldn't help but wonder, yet again, why this incredibly useful, simple data structure, which also didactically demonstrates some very nice concepts like one-sided error and the ability to trade off speed/memory with correctness, isn't in the standard undergraduate textbooks?  (Of course, you can always buy this book....)

If you're teaching algorithms and data structures, do you students a favor, and sneak Bloom filters in one lecture. 

Stuff in press

The Economist has a special section this month devoted to The Data Deluge.  (Much of it may still be behind their firewall.)  Many computer scientists are quoted/named in the collection of articles, and it gives a nice overview of what's going on generally.  (It makes a horrible mistake, though, by saying that Google's original advance was counting the number of links to a page to score relevance;  that ignores PageRank, and Altavista...)

Bach, Chawla, and Umboh take our previous work on the hiring problem in new directions.  Or, even, new dimensions:  they also consider multidimensional variations of the problem.  It's definitely a general problem with plenty of variations to consider;  perhaps this paper will inspire further looks at the problem.