Student Bragging....

Always worth bragging about my students...

Justin Thaler's paper "Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability" (with me, Michael Goodrich, Dan Hirschberg) was accepted to TAPAS 2000 (now called MedAlg 2012 (link to the new site), after a conference renaming).  So he's won an all-expense paid trip (well, paid for by my grants) to Israel.  He'll be amortizing the trip by giving a few other talks while he's there, so look out for him in December.

Recently graduated Zhenming Liu had his paper with Sharon Goldberg on "The diffusion of networking technologies" accepted to SODA 2013.  It's a very interesting variation on diffusion by social spreading phenomenon, asking what happens when the issue determining whether you adopt a new technology is not how many of your neighbors are using it, but how many users you can reach (in your connected component) are using it.

And Giorgos Zervas (postdoc) has his paper "An Economic Analysis of User-Privacy Options in Ad-Supported Services" (with me and Joan Feigenbaum) accepted to WINE 2012.  We were looking at when ad-supported services could be economically motivated to offer stronger privacy options (e.g., no targeted ads) that earn them less per user, either because it would encourage more users to join or because of competition.

Sadly, the only recent rejection is my own SODA submission -- which was rightly sent back to me, but that's the subject of another post.

By the Numbers

Pretty much matching my predictions....

My graduate course has 50 enrolled right now, fairly close to 50-50 between undergrads and grads.

Salil's introductory complexity course currently has 129 -- far and away the biggest the class has been in my memory.

And our "flagship" introductory course, CS 50, grew yet again, to 746 students.  That would, for the first time (and slightly ahead of my schedule), make us larger than the introductory Economics course, EC 10.  (The 746 includes graduate students and even some people from the business school, so it might be a "win" on a technicality, but we'll count it as a full win.)  

Back to work now -- class to prep!

Happiness Is...

NSF saying yes to your grant... (Isn't that one of the lyrics?)

Once again, thanks to the NSF, I get to remain in business* for the next 3-4 years or so.  (Arguably, a large chunk of the thanks also goes to my colleagues Michael Goodrich and Roberto Tamassia, who allowed me to ride on their long coattails this time.  The grant is CNS-1228598, Privacy Preserving Distributed Storage and Computation -- might as well start putting it in all my documents now!)  

This makes up a bit for my sadness a few months ago, when NSF rejected the other grant proposal I sent in this year.**  Given NSF odds these days, I'm more than excited to go 1 for 2 for the year.  Especially since I've run into the following scenario previously:  I'm at the point where I have about a year plus before my grants will disappear;  I send in proposals and they don't get funded, so I'm a little concerned.  So far when that's happened I send in proposal again the next year, before the money runs out, and the NSF funds something and I'm fine again.  This time through the cycle, I'm not going through that, "Gee, something really better get funded, or..." panic scenario that previously has run through my head.

The other grant rejection, though, still stings.  It was written with a colleague with whom I've written many, many successful papers, one of which has won a major award, another of which has seen some major media attention.  In fact we've written several proposals together... none of which has been funded.  There are undoubtedly reasons for this -- our joint work tends to be interdisciplinary and very speculative, and our proposals are often written about things we dream of working on rather than a more grounded, "Here's exactly what we'll do" level that I find is needed to get at least my proposals funded.

And this summarizes my love-hate relationship with the NSF -- which, admittedly, has a lot, lot more love than hate.  The NSF has always come through for me -- they've funded me steadily since I started as faculty.  On the other hand, they're very much a black box to me -- I still don't have a great idea of what will "work" for them and what won't, so I have to keep sending stuff in and coping with rejection.

Which reminds me -- time to think about what, if any, grants will go in this year.  Medium deadline is soon (Oct 9), but the small deadlines are a ways off (Dec)...


* The research business, that is.
** I also was part of a group that submitted a DARPA proposal, which didn't get funded, but that didn't really cause me sadness, as I've come to expect not getting money from DARPA.

But I had to grow bigger. So bigger I got.

First day of lecture for CS 222, Algorithms at the End of the Wire.  They stuck me in a classroom that holds 20 comfortably, and 25 or so can be done.  I'm pretty sure well over 50 showed up.  We're still going through increases in the CS student population, and there's a shortage of CS classes this fall due to various leaves and such, so I'm expecting a larger class than usual.  When I first taught the course in 1999 it had something like 45 people;  it may be bigger this time.

Salil Vadhan had it better/worse (depending on how you look at these things).  He's teaching the intro theory class (complexity classes, Turing machines, etc.), and the room was well over-full.  Last year's class size was about 70;  I imagine he'll end up with between 100 and 150 this year, and the upper end of that range wouldn't surprise me.

It's exciting to see CS growing like this again.  I like seeing the large classes, all the student interest.  The more the merrier.  I'm eagerly awaiting the final enrollment numbers for CS this year.  Still, the nagging worry in the back of my head: anyone know when the next CS bust is going to take place?

Uncertainty

There's an interesting new article on the Gov 1310 case* on the Crimson yesterday, titled Students Accused  in Cheating Scandal Frustrated by Uncertain Process.  Well, of course the students are frustrated, but I think it's somewhat unfair to call the process "uncertain", so I'd like to go through this a bit and consider the complaints.

Before getting to specifics, some generalities.  These complaints are not new to this case;  the issue of the "uncertainty" of the Ad Board comes up all the time.  While I try to be sympathetic to the complaint, this is just a fact of life.  While I dislike resorting to the natural framework that the Ad Board is like a legal proceedings, because in some ways it very much is not, it is in some ways.  Evidence must be gathered and weighed.  This takes time, and there are participants' schedule to juggle (students as well as administrators), so there is uncertainty in when decisions will be reached.  There are rules providing for outcomes depending on what decision is reached, so in some sense the possible outcomes are known, but of course one does not know what the decision will be ahead of time.  As someone who has spent some time involved in legal proceedings (fortunately, as an expert witness, not as a defendant), I am aware that "uncertainties" in timing and outcome are an essentially unavoidable part of the process.  It is arguably the price for having a body do its best to carefully and fairly reach a judgment on what has occurred and how the rules apply in the circumstances.

So now let's look at specific points of the Crimson article.

First, it is reported the Secretary of the Ad Board had told a student they could expect to receive a verdict by November.  I understand that's a long time, but that appears to be the outcome of having so many cases to deal with.  In a standard setting, I believe the Ad Board tries to resolve such cases in a small number of weeks (often 1-3), depending on how many students are involved.  Here, there's a bottleneck.

"The student said he feels the Administrative Board process has left him unable to make plans for the new semester that begins on Tuesday as he waits to hear whether he will be forced to withdraw from Harvard."

While I understand, that sucks, how exactly could the process change?  

Well, there is actually a suggestion in there -- the Ad Board doesn't (and didn't) meet over the summer, but there's the suggestion that the administrators should have been "called back" to work on the Gov 1310 case during the summer.  I'm not sure if the Ad Board considered that, or if it would have been feasible.  Were I currently serving on the Ad Board, for example, Harvard would have trouble "calling me back" at various points over the summer, when I'm traveling.  These administrators have other obligations and duties;  Ad Board is not their full time role.  But perhaps this is a valid point of criticism.

Another thing they could do is try to put more bodies on the problem now.  Again, I'm not sure how feasible that is;  it wouldn't fit in with how cases are normally run (eventually, the Ad Board as a body has to meet and vote on cases), and I can see all sorts of potential problems bringing in other administrators or faculty members not familiar with the Ad Board process to try to deal with this specific case.   So again, while this is perhaps a valid criticism, realistically, the students have to understand that all this takes time, given the large number of cases, and particularly since a goal is to have the right outcomes, which means careful study of each individual's situation by multiple people.  

Another uncertainty complaint comes from a recent graduate who received notice that they are being investigated, who apparently is not clear on what punishments might be forthcoming.   

“It’s unfair to leave that uncertainty, given that we’re starting lives,” said the alumnus, who was granted anonymity by The Crimson because he said he feared repercussions from Harvard for discussing the case. “It’d be a huge financial and emotional hardship…. If my degree was threatened, I would not take that lightly.”

It's an interesting question whether a degree can/should be taken away for cheating after the degree has been granted.  I admit, I would have to ask the administrators if this is possible, but my understanding is that while temporarily rescinding a degree is rare it is a possible punishment.  (Essentially, the student would have not been in "good standing" at the time of graduation, which means they couldn't have received their diploma.)  But I'm not clear what the alumnus is complaining about.  If the issue is whether they are uncertain as to whether it's possible their degree would be rescinded (until such time as they are back in good standing -- this would not keep them from their degree permanently, if I understand properly), a call to their Ad Board representative should clear that up.  If the issue is that they are upset that the outcome is uncertain, again, the Ad Board has to gather evidence, discuss, and reach its conclusion, and I'm sure they're working hard to do so as quickly as possible.

One other interesting complaint is that a student thought Harvard should not have made the Gov 1030 case public;  it makes it difficult for students who voluntarily or involuntarily withdraw to keep their involvement confidential (for example, to potential employers).  I think this is somewhat unrealistic.  With so many people involved, this was going to reach the public's ears eventually, whether Harvard made the announcement or not.  And employers generally seek information regarding reasons when a student leaves campus for a prolonged period;  students must face that they may have to discuss the issue when looking for jobs or in other cases where their record might be examined.  

I imagine I may be appearing unsympathetic to the students;  this is not the case.  Particularly in this case, I'm sure there are many students who will be completely absolved, and they will have gone through significant stress along the way.  Unfortunately, these things happen -- while students might not yet realize it, most people at some point have similar unpleasant run-ins with various bureaucracies.  Blaming the Ad Board for uncertainties that appear inherent to the process, while completely understandable given the stress and emotions involved, seems misplaced.        


* I've been trying to avoid referring to it as a "cheating scandal" since, as far as I can tell, nobody at this point has been required to withdraw for academic misconduct.  Hence for now it's the Gov 1030 case.

Honor Codes?

A further interesting question that has come out of the as-of-yet alleged cheating scandal at Harvard is whether Harvard should have an honor code.  The question is particularly interesting since Harvard attempted to institute a voluntary "freshman pledge" last year, that met with "controversy" (see here, here for example).  Harry Lewis wrote a detailed opinion of the pledge on his blog at the time.  Indeed, Harry Lewis in fact has spoken consistently on this issue for some time -- here's a 1996 Crimson article where he is quoted:

"Our understanding is that in registering at Harvard students agree to abide by the rules of the community they are voluntarily entering. It is not clear why a special signed agreement of another kind would be needed, or would add anything."

As if often the case, I agree with Harry's opinion above.  Also, I'd much rather have students discussing the issues and coming to grips with what are sometimes challenging ethical questions rather than signing a pledge.   

Come to think of it, I'm not sure if freshmen are to be asked to sign the pledge again this year.  (The pledge is not an honor code per se, but has been called the "kindness pledge".)

But back to the question.  Should Harvard have an honor code?  Why?  What would it add?  More empirically, do honor codes actually reduce bad behaviors, like cheating?  Is there evidence of it?  I note that many cheating scandals have occurred at schools with honor codes -- like the Naval Academy and Duke -- though apparently some researchers suggest an honor code could reduce cheating.

A natural question:  should punishments be more severe for cheating if cheating is part of an honor code?

Clearly, the question of whether we should have an honor code is going to arise at Harvard this year.  Any opinions in advance?

Max Flows in O(nm) Time by Orlin

Just saw Suresh point to this talk (and paper) about a new result for max flows in O(nm) time by James Orlin.  I'm listening to the talk he has on line this afternoon, but it seems buzzworthy and I hadn't heard about it, so I thought I'd add some buzz.  

Academic Dishonesty Cases

I have a bunch of half-written blog posts, none of which I have felt pressed to finish, so the blog has languished over the summer.  But then, something has come up worth writing about.

The Harvard Gazette has an article up about a cheating scandal at Harvard;  apparently, in a large class last spring, a large number of students worked together on the final exam.  The first two paragraphs read:

The Harvard College Administrative Board is investigating allegations that a significant number of students enrolled in an undergraduate course last semester may have inappropriately collaborated on answers, or plagiarized their classmates’ responses, on the final exam for the course.

An initial investigation by the board, the faculty committee charged with interpreting and applying the rules of the Faculty of Arts and Sciences to the undergraduate student body, touched off a comprehensive review of the more than 250 take-home final exams submitted at the end of the course. That review has resulted in cases before the Administrative Board involving nearly half the students in the class.

This is reminiscent of other past scandals (MIT, Duke) and general trends found in examining academic dishonesty (Stanford, MIT).

There's not much information out there right now on this story -- Harvard has not even released what class is involved.  There aren't that many classes with an enrollment > 250, so it might not be too hard to piece together;  I imagine some newspapers will find out soon enough.  (Update:  The Crimson tweets that the class is Introduction to Congress.)

There are a number of ways to look at this story, and I imagine I might write a few posts on it.  One issue is the fallout for the students.  Harvard has a very tough policy on academic dishonesty compared to other schools, from what I've heard.  A standard punishment is that students are required to withdraw for one year for cases of plagiarism.  "Improper collaboration" is perhaps a bit fuzzier an issue, and I am not sure how the Ad Board will choose to handle it.  But it will certainly be a stressful and trying time for all involved as it gets sorted out, and for those with more severe punishments, well afterwards.  I note that it's not just the students who have to deal with the stress of it all;  it also takes the toll on the administrators who have to administer these decisions.

Are Harvard's remedies for academic dishonesty too strict?  These are the rules of the Faculty, and we could change them.  Is withdrawal for 1 year for standard cases suitable?  I've heard many arguments (generally from students) that that is too harsh a sentence;  on the other hand, it's meant to strongly deter what should be (but doesn't seem to be) a rare transgression.  It's an interesting issue to consider, and I'd enjoy hearing reasoned views in the comments.

Interestingly, there's been a lot on higher-up academic dishonesty of various sorts of late, most notably Fareed Zakaria (Yale Daily News, one of many Shots in the Dark Posts) and Niall Ferguson (Brad DeLong's blog,one of many Shots in the Dark posts).  So these topics seem ripe for larger-scale discussion.    

Important IP Case

For those of you not following the Apple-Samsung case going on right now, it's fascinating.  Since I do expert witness work, it's interesting to me from that perspective, but just in terms of the technology and issues involved, there seems to be a lot involved in the case.  FOSS patents has detailed coverage, although it's also getting plenty of detailed coverage from business and tech news sites.

In particular, the latest things that really interested me:

Harvard's own Woody Yang (Electrical Engineering) was a witness for Samsung. 
(It's been several years since it happened, but when I started at Harvard, I ran into many uninformed people who didn't seem to know that Harvard had computer science and engineering.  So when a Harvard prof shows up in such a high-profile context, it still makes me smile.) 

Andries van Dam used Mitsubishi Electric Research Lab's Diamondtouch as prior art for the snap-back patent.  (See here, here, here.)  I spent a good deal of time at MERL around that time period, and remember they were (rightly) very excited about it as a technology, so it's interesting to see it come back as a piece of prior art in this case.

Mail Issue

Last week I had an issue where I sent an e-mail to someone (non-work-related), and a while later got the response forwarded to me from my wife, with a note that Harvard was rejecting the response e-mail.  It seemed to be a one-time issue -- I was getting other e-mail -- so I assumed it was a spurious issue and ignored it.

Last night, it happened again -- both of my brothers had their mail to me bounced from Harvard, with the same error message.

The commonality was easy to spot -- all were using Yahoo mail accounts.

I sent mail to IT, who quickly found that yes, a firewall upgrade last week had somehow made mail from mail.yahoo.com undeliverable.

It's always a little disturbing to me when I find these problems.  For historical reasons I think I'm on a mail server that doesn't involve a large number of people at Harvard, but still, nobody noticed for a week that mail from Yahoo wasn't being delivered?  Perhaps it says something unfortunate about how many people still use Yahoo mail accounts these days.

It's also an example of something I feel I always have to explain to people:  e-mail is not a 100% reliable delivery service, and shouldn't be thought of as such.  Yes, most of the time if your e-mail is dropped it is a "me issue" (you can either view it as my laziness/irresponsibility, or view it from my standpoint -- I get 50-100 e-mails a day and yours fell off the end somewhere);  and sometimes these days it's a system issue (your mail looked like spam, and never reached my eyes).  This time at least there was an error response so it was known that the mail didn't get through.  But always best to be wary of your e-mail system, and use the phone if it's something important you need a response to.

 

Distracting Videos

Jeff Erickson gets the blame for pointing out this amusing/disturbing video on counting.  I feel like I should make it a background video before my undergraduate class one day.  Catchy tune.  

My wife liked this backyard roller coaster video, which apparently creates discussion about whether this is the best dad ever (let me repeat:  backyard roller coaster) or completely irresponsible and dangerous parenting (let me repeat:  backyard roller coaster).  

David Malan gets fun videos up to advertise CS50.  So any Harvard students reading this, point the freshpeople over to www.cs50.net and run the video.  (In this case, I will not justify the choice of music.)  Expect more CS50 goodness and news on the blog as it's one of the initial HarvardX courses.  

I found my library had all the Sarah Jane Adventures DVD sets.  (Trailer here.)  For those who don't know, Sarah Jane Smith was one of Doctor Who's companions back in the 1970's;  only three decades or so later, they finally gave her a spin-off show, which is a lighter and somewhat more kid-friendly version of Doctor Who.  My kids (who also like Doctor Who, though they're occasionally creeped out by it) were instantly addicted when we visited London a few years ago.  So this last week or so I've been forced to watch many, many happy hours of perfectly summertime TV with the kids.  (My youngest only wants to watch Scooby Doo, so I've also been catching the new episodes of Scooby Doo! Mystery Incorporated -- EVIL PIZZA ;  while I'm really, really, really burnt out on Scooby Doo at this point, I have to say, the Mystery Incorporated series seems like the best incarnation of Scooby Doo ever.)

Article about DEC Folk

Interesting Wired article talking about a bunch of people I worked with back when I was at Digital Systems Research Center, and their big effect on Google.  It's great to see them get credit for all they've done.

Like a Movie Meteor...

The new semester is hurtling toward me.

This semester I get to teach one of my graduate courses, the one I named Algorithms at the End of the Wire sometime over a decade ago, when that seemed like an appropriate title.  Students seem to have learned that the appropriate subtitle for the course is something akin to:  "Things Professor Mitzenmacher is working on, is interested in, or otherwise likes."  Standard topics therefore include ranking and search engines (Pagerank + variants), data sketches and summaries, coding, and compression.

Since I teach it every other year, I try to introduce new topics into the mix where appropriate.  Generally, I'm looking for two things:

1)  Topics that have an interesting mix of theory and practice.  The class is based on paper-reading, so it's particularly fun (for me) to try to find a topic where I can assign one theoretical paper and one practical paper.  This yields interesting room for comparisons and contrasts, induces (I can only hope) interactions between systems and theory students in the class, and (again I can only hope) ensures that everyone gets something out of at least one of the papers.
2)  Topics in my bailiwick.  Networking (including social networking!) is always good;  connections between "EE theory" and "CS theory" are nice;  big data topics, including database or cloud style applications are very welcome.

So what papers in the last 2-3 years, say, really need to be added to the class reading list?  Where are the new and exciting places where theory and practice are meeting to produce exciting breakthroughs (that, ideally, can be covered in couple of lectures)?  Or, as another way to think about it, what should I really be learning about?  Please let me know in the comments.    
 
PS:  Yes, I haven't been blogging much.  I've been having a perfectly enjoyable summer without blogging.  I've been busy with vacation, kid time, other lazy time, consulting work, the occasional bit of "Area Dean" administration, and, of course, my day job -- a few papers have been submitted, a few more are at various stages in the pipeline.  But I suppose with the summer tailing off I'll have more reason to be blogging again. 

Yale Daily News, continued

I pointed to this article in the Yale Daily News about computer science when it came out in April.  Giorgos just pointed me back to it again, and I'd have to say, it's worth looking at again for the comments, which I'm still trying to grok.   

MMDS

I'm hanging out at MMDS -- the Workshop on Algorithms for Modern Massive Datasets at Stanford.  The crowd is surprisingly huge, with a greater number of people in "adjacent" areas (math/statistics/machine learning) and industry than is normal for me.   It's very exciting to see such wide-scale interest.

Right now, though, the non-theorists are having to listen to a very theoretical session:

11:00 - 11:30 Ping Li Probabilistic Hashing for Efficient Search and Learning on Massive Data 11:30 - 12:00 Ashish Goel Real Time Social Search and Related Problems 12:00 - 12:30 Andrew Goldberg Hub Labels in Databases: Shortest Paths for the Masses

Fun stuff!

I just enjoyed an interesting aspect of Ashish's talk.  He was putting the social search problem in a framework where you first do preprocessing on the social graph (using distance oracles for shortest paths), and then do incremental updates (corresponding to when someone say does a new Tweet, you update the keywords associated with that user).  I like it because I talk about the preprocessing + query answering approach (using examples like suffix trees, least common ancestor data structures) in my undergrad class.  This preprocessing + incremental update + query answering example in the context of social search would make a nice addition (that students can hopefully appreciate), if I could simplify it in a reasonable way.

On NPR (Morning Edition)

Groupon is being discussed on NPR (Morning Edition), which means we get a phone call again.  Our graphs are reproduced on the site, and John Byers speaks for us (Giorgos and me with John).

Anniversary

Today I get to celebrate that I'm two years done with my three year stint as "Area Dean for Computer Science" (chair).  Whoever the new person is, they're supposed to start July 1, 2013.  I've already starting encouraging the possible successors to step up.  (Indeed, I've already started to become a bit more ambitious.  I'm hoping to line up the next 3 or 4 people for the position;  no tag backs for a decade...)

It's not that I'm unhappy with the job.  (I realize that statement is a no-op;  I have to say that.  I'm trying to get others to take over.)  I'm pleased with what I've been able to do.  We tenured two faculty last year (Hanspeter Pfister and Radhika Nagpal);  we promoted another (Yiling Chen);  we hired a new faculty member (Yaron Singer);  and we've just had a junior faculty search for next year approved.  We're (still) a relatively small department with a lot of demands on us, and I came in with a clear goal for us for faculty growth.  I feel we've been successful in this regard.  There have been some other nice successes, such as the new SEAS Design Fair I helped manage and organize, which I expect will be an annual event.  And I'm able to act as the faculty interface with the administration in various ways, helping, I hope, keep things running smoothly.

But I'll also be happy to step down.  I'm overdue for a sabbatical already (the price of agreeing to a 3-year job).  I'll enjoy getting the time back for other things.  (Though I expect I'm being unrealistic, and that some other committee or administrative task will try to absorb the time.)  I like the "serve 3 years and out" model (though I see weaknesses in it too, in terms of setting up longer term infrastructures).  I enjoy taking on new experiences and challenges, so trying out "management" (if that's what this job is) has been interesting and educational.  But in one more year, another change will be good.

    

Simons Institute Call

Alistair Sinclair asked me to post the call at http://simons.berkeley.edu/cfp_summer2012.html for the Call for Proposals for Simons Institute programs.  The deadline is mid-July.

Worth noting --  two semester-long programs for Fall 2013 are already decided: these are "Real Analysis in Computer Science," organized by Gil Kalai, Subhash Khot, Michel Ledoux, Elchanan Mossel, Prasad Raghavendra and Luca Trevisan; and "Theoretical Foundations of Big Data Analysis," organized by Stephen Boyd, Peter Buehlmann, Michael Jordan, Ravi Kannan, Michael Mahoney and Muthu Muthukrishnan.  Get your tickets now.

New SIGACT Officers

Lance informs me we have newly elected officers at SIGACT.

Chair:  Paul Beame

Members-at-Large:

Venkatesan Guruswami
Rocco Servedio
Avrim Blum
Tal Rabin

Congratulations/condolences to the winners.  I'm sure Paul will do a great job --
he's a regular commenter here, and I always find his opinions incredibly well thought out,
even in (rare) cases where I disagree.  I can't wait to see what he does.

I'd also like to thank Lance for his service as chair the last few years.  He had the unenviable
job of keeping the community happy, preserving the structures that have served us well while
trying to introduce new ideas where there looked to be room for improvement.  I think he's
done a great job, generating some controversy and discussion while keeping everything moving forward.  He (and the other SIGACT volunteers) deserve our thanks.  So, thanks!

Mihai Memorial Blog

I received the following note from Mikkel Thorup and Alexandr Andoni.
I believe it's appropriate to share:

Dear friends of Mihai,

We made a blog in Mihai's memory. Celebrating Mihai's energy and
spirit, please cheer him with a glass of wine (or other spirits), and
send in a picture to be posted on the page:
http://mipmemorial.blogspot.com

Best regards,
Mikkel and Alex

Many of you have left wonderful comments about Mihai here.  I hope you'll copy them over and possibly add to them at the memorial site.