Some Recent Books

If you've been reading the other computer science blogs, you know that there are some new books out.

First is the The Golden Ticket: P, NP, and the Search for the Impossible, by Lance Fortnow, about the P vs. NP problem.  I got sent a review copy;  I haven't read it yet, but I'm testing it out by having my oldest daughter read it and tell me what she thinks, and I'll read it along with her.

Then there's Quantum Computing since Democritus, which covers complexity theory, quantum computing, cryptography, and a bunch of other stuff.

But there's more!  Thomas Cormen, of the famous CLRS Introduction to Algorithms book, has a new book out called Algorithms Unlocked, which seems to be a friendly introduction to the basics of algorithms.


On the popular books front, Eric Schmidt (yes that one) and Jared Cohen have a book out on The New Digital Age: Reshaping the Future of People, Nations and Business.

Also, the book Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers, from some time ago, is out in paperback.



On the textbook side, last year Steven Gortler of Harvard introduced a new textbook for computer graphics that looks really good.  And of course, there's always that Mitzenmacher/Upfal Probability and Computing: Randomized Algorithms and Probabilistic Analysis to buy if it's not already on your shelf...

Thanks for the Memories....

I'm off to a meeting next week, so today was my last day of class for Computer Science 124 (Algorithms and Data Structures) for the semester.  For two reasons, today feels important. 

First, because I'll be on sabbatical next year, I won't have to teach another lecture for what seems to be something like 18 months.  I haven't had that much time off from teaching since I've started.  I'm looking forward to it, especially as this year the administrative job has slowed research.  I'm hopeful the sabbatical time can be put to use productively on the research side.

Second, more nostalgically, I've taught this class for the last 15 years.  To me that feels like a record of some sort.  When I come back from sabbatical, the plan is that someone else will be teaching the course, and I'll have to find something new and entertaining (for me, and maybe for the students) to teach.  I admit, my preference would be to teach this class pretty much forever.  After 15 years, I finally think I'm starting to understand all the material and how it fits together.  I'll miss the class.  While my head knows that it is probably good for both me and the class to separate, my heart hurts a little, giving it up and moving on.     

Given the excitement of once again being done with teaching for the academic year, I'm sure I'll get by.  (As I explain to the students, the only ones happier than they are that classes are ending are the faculty...)  Things change -- obviously, for me, sometimes very slowly -- and I'm optimistic that whatever I decide to teach next, I can make it a course I'll enjoy teaching for say the next 15 years.

Guest Post by Mark Bun and Justin Thaler

Michael asked me and Mark to write a post on our paper "Dual Lower Bounds for Approximate Degree and Markov Bernstein Inequalities", and we're happy to do so. As the title suggests, our paper focuses on understanding a certain measure of the complexity of a Boolean function, known as approximate degree. Given an n-variate Boolean function f, the approximate degree of f is the least degree of a real polynomial that pointwise approximates f to accuracy 1/3 (the choice of the constant 1/3 is by convention -- the particular constant is inconsequential).

Aside from being a natural complexity measure, approximate degree has a surprisingly wide range of applications throughout theoretical computer science. A very partial list includes:

1) Lower bounds on approximate degree yield lower bounds on quantum query complexity.

2) Lower bounds on approximate degree have recently been used to resolve long-standing open questions in communication complexity (see here for a survey from 2008, and some more recent works here and here).

3) Upper bounds on approximate degree underly the best known agnostic learning algorithms.

Despite the range and importance of these applications, large gaps remain in our understanding of approximate degree. The approximate degree of any *symmetric* Boolean function has been understood since Paturi's 1992 paper, but once we move beyond symmetric functions, few general results are known. One function that has served as a symbol of our lack of understanding is the two-level AND-OR tree, the function computed by a CNF (i.e. an AND of ORs) with all gates having fan-in sqrt(n). Over the last couple of decades, there has been a line of work proving incrementally larger lower bounds on the approximate degree of the AND-OR tree, with the best previous lower bound being Omega(n^{3/8}) due to Sherstov. Our main result in the paper resolves the question completely by establishing an Omega(sqrt(n)) lower bound, matching an O(sqrt(n)) upper bound due to H\oyer, Mosca, and de Wolf. (Sherstov recently independently obtained the same Omega(sqrt(n)) lower bound using related techniques). Our second result is to give a new proof of Paturi's lower bound for symmetric Boolean functions.

Let us say a bit about how our proofs of these two results work. Traditionally, approximate degree lower bounds have been proven by a technique known as symmetrization, which transforms questions about multivariate polynomials into well-understood univariate ones. In Step 1, one supposes there is a n-variate polynomial p that pointwise approximates f to error 1/3, and turns it into a univariate polynomial q in such a way that deg(p) >= deg(q). In Step 2, one shows that q must have high degree, which means p must have high degree as well. Unfortunately, the symmetrization step of moving from p to q often 'throws away' information about p (after all, p is an {n choose d}-dimensional object, and q is only a d-dimensional object), so one sometimes runs into problems in completing Step 2.

Recently, there has been progress in moving beyond 'lossy' lower bound techniques like symmetrization. Our paper uses the following approach, which is completely lossless. You can straightforwardly formulate the approximate degree of a function f as a linear program: the approximate degree of f is at least d if the value of the following LP is larger than 1/3:

min \epsilon

s.t. |f(x) - \sum_{|S| <= d} c_S chi_S(x)| <= epsilon, for all x in {-1, 1}^n

c_S in \mathbb{R}

Here, chi_S(x) is the parity function over variables in the set S. This program is just asking you to construct a degree d polynomial that minimizes the distance to f under the L_{\infty} norm.

If you take the dual of this program, what you'll find is that the dual is asking you to construct a function p that has *zero* correlation with every degree d polynomial, but has large correlation with f. We call such a polynomial a "dual polynomial" for f, as one can think of p as a polynomial with no monomials of degree d or less. A dual polynomial for f is a 'witness' to the fact that f has large approximate degree. By strong LP duality, any approximate degree lower bound entails the existence of a good dual polynomial; it might just take a lot of work to find it! Both of our results -- our Omega(sqrt(n)) lower bound on the approximate degree of AND-OR, and our new proof of Paturi's result -- work by constructing explicit dual polynomials.

In the case of the AND-OR tree, we take a dual polynomial for AND, and a dual polynomial for OR, and we combine them in a certain way to get a dual polynomial for AND-OR. Our proof is a refinement of a technique of Sherstov -- Sherstov had already showed in a very general context the 'right' way to put together dual polynomials for simpler functions F, G to get a dual polynomial p for their 'block-composition' F(G, G, ..., G), but his earlier analysis could not handle the case that F=AND and G=OR. Prior work broke down because it was not known how to argue that p had high correlation with AND(OR, OR ..., OR). We manage to show this by exploiting some special properties of the AND function and the OR function (specifically, the key properties are that AND has low block sensitivity at all inputs except the All-True input, and dual polynomials for OR have 'one-sided error'. It's difficult to give much more detail than that in a blog post, so see the paper for the full discussion.)

We construct our dual polynomial for symmetric functions as follows. \v{S}palek , building on work of Szegedy, had already constructed a dual polynomial for the OR function i.e. a symmetric function with a 'jump' from +1 to -1 at the bottom Hamming layer of the hypercube. We give a relatively simple construction of a dual polynomial for the Majority function i.e. a symmetric function with a 'jump' from +1 to -1 near the middle Hamming layer of the hypercube. We then show how one can interpolate between these two 'extreme' constructions to give a dual polynomial for an arbitrary symmetric function f. Our final dual polynomial closely 'tracks' (in a sense that can be made precise by complementary slackness) an optimal approximating polynomial for symmetric f's, and we are planning on adding a section to the arxiv paper explaining this intuition.

Finally, we use LP duality to reprove some classical Markov-Bernstein type inequalities from approximation theory (not to be confused with Markov's Inequality or Bernstein's Inequality from elementary probability theory). Markov-Bernstein inequalities bound the derivative of a univariate polynomial q on real inputs in the interval [-1, 1] in terms of deg(q) and the maximum value q takes on this interval. Typically, these are the inequalities used to complete Step 2 in the outline of symmetrization arguments given above. We show how to formulate the problem of maximizing the derivative of a bounded polynomial as an LP, and give clean solutions to the dual LP that 'witness' various asymptotic versions of the Markov-Bernstein inequality. The connection between Markov-Bernstein inequalities and LPs has certainly been known before, but to our knowledge no one has proved these inequalities by analytically constructing dual solutions to these LPs, and we think our dual witnesses shed some new light on these well-known results.

Looking ahead, we're very optimistic than more open problems in the analysis of Boolean functions can be cracked using methods based on LP duality. Approximate degree is not the only measure of the complexity of a Boolean function f that can be characterized by a linear program: there's also polynomial threshold function (PTF) degree (i.e. the minimum degree of a polynomial that sign-represents f), PTF weight-degree tradeoffs (i.e. tradeoffs between the degree of a PTF for f vs. the size of its coefficients), and weight-degree tradeoffs for polynomials that approximate f pointwise to accuracy 1/3. All of these complexity measures have important applications in learning theory, communication complexity, and beyond, but remain poorly understood even in the context of simple function classes like AC^0.

This work was not done in a vacuum, and we are extremely grateful to Karthekeyan Chandrasekaran, Troy Lee, Sasha Sherstov, Robert \v{S}palek, Jon Ullman, Andrew Wan, and the anonymous ICALP reviewers for valuable comments and conversations! As well as to Ryan O'Donnell and Li-Yang Tan for suggesting the problem of constructing explicit dual witnesses for the LPs capturing Markov-type inequalities!

Congratulations to Mark Bun and Justin Thaler

Luca Aceto reported the paper awards for ICALP 2013.  But I find it necessary to give a special shout-out to Harvard Ph.D. students Mark Bun and Justin Thaler, who got the Track A Best Paper Award for their work:
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. 

I've asked Justin and he has agreed that he and Mark will write up a post about their paper that will appear in a few days.  But since it was announced I wanted to congratulate them now!  

This brings up an interesting question:  they won the Best Paper award, but not the Best Student Paper award.  Which makes some sense in one way -- if the "Best Paper award" dominates the "Best Student Paper award" (by definition), then there's not need to give the same paper two awards;  it has the nominally higher honor.  On the other hand, you might say that if they won the Best Paper award, by definition they should also have the Best Student Paper, so they should win both.  How do you think awards in that case should be distributed?

  

Guest Post by Mikkel Thorup : Results vs. Techniques

[Mikkel Thorup graciously has offered a guest blog post, discussing what he looks for in conference papers, and possible implications for refereeing.]


Results versus Techniques (Mikkel Thorup)
-------------------------

When I go to STOC/FOCS, I hope to see some great new results/theorems and some great new techniques/proofs. I want both, and in some wonderful cases, I even get both in the same paper. However, many of the greatest results may be in papers with less interesting techniques, or vice versa, and the worst thing is if they then get out-competed by papers achieving semi-strong results using semi-interesting techniques.

I am saying this because many refereeing forms have fields like "Submission's strengths" and "Submission's weakness" suggesting a balanced evaluation with pros and cons. A common case I see is that strong results get criticized for being obtained with too specialized techniques. However, if somebody needs to cite a theorem/result, then, typically, it doesn't matter if the underlying proof/technique is specialized.

I am arguing that if we want an interesting program, then we should not worry about weakness unless it renders a paper unacceptable (e.g., a bug). I am proposing a max-evaluation rather than a sum. What matters is if a paper has an exiting contribution.

I am myself mostly in the problem solving business where we believe that there are important computational problems. Sometimes general techniques work, but other cases require a deep understanding of the problem at hand leading to very problem specific techniques. Sometimes a tiny but subtle change in existing techniques can make a huge difference. Other times, as, e.g., for the 4-color theorem, it seems that what is needed is a huge mess. The point here is that if we want to succeed, then we have to be open to use whatever techniques it takes. Later there may be very interesting technical work simplifying and generalizing the techniques.

I am not saying that techniques are not important. I love papers introducing great new techniques, and I am more than happy to accept them on a technical basis. What I am saying is that if the main contribution of a paper is a result, then the techniques may play a more supporting role whose only obvious merit is that they prove something interesting.

It often turns out that the techniques developed to solve a central problem have other applications, but this may not be easy to guess up front based on a quick review. My experience is that referees are worse than random when it comers to guessing if a techniques will later prove useful in solving other problems.

My suggestion is positive refereeing where the overall score is based on the major contribution of a paper: the thing that would make people come to the talk, and use and cite the paper in the future. If a paper has something interesting to say, then it doesn't matter if other aspects of it are less interesting.

Upcoming Events

I've been asked to post for some upcoming events.

The Simons Institute will have a multi-day symposium on Visions of the Theory of Computing May 29-31, just before STOC.  Looks like a lot of big-name speaker.  More info here.

Ely Porat wants a lot of submission for SPIRE's 20th conference;  paper dealing is May 2.  Call for papers.  http://u.cs.biu.ac.il/~porately/spire2013/

Harvard E-Mail, Again

Yesterday was the long-awaited faculty meeting after the news that Harvard had examined the e-mail (metadata) of the Resident Deans looking for a leak of what was labelled confidential information. 

It was actually quite informative.  The most detailed account seems to appear (unsurprisingly) in Harvard Magazine.  To me, here are the highlights:

1)  Deans Smith and Hammonds gave unambiguous, complete apologies.
2)  There was a bit more e-mail searching than originally described;  in particular, there were some follow-on searches on the e-mail accounts of a Resident Dean that definitely did not go through the full process (specifically, Dean Smith doesn't appear to have been informed of them). 

I think the clear and unambiguous apologies were needed.  While I think I have been understanding throughout about why the administration felt the leak issue was important enough to merit e-mail searches, the fact was that Harvard's written policies were not followed.  That alone merits the apology.  Given that the previous apology offered by the administration was described by many as "half-hearted", it was important to have a full apology given at the meeting.  (Let's leave aside that it seemed a bit slow in coming.) 

It's a bit more disturbing that the institution doesn't seem to have a complete handle on process for searching electronic communications, but then again, it's a fairly new topic.  It's clear that this will be address on an ongoing basis, with an outside attorney investigating the past actions, and a Harvard committee being set up to examine the institutional policies regarding privacy of electronic communications.

Anyhow, seems like progress.

Harvard in the NCAA Tournament

Thank goodness it's Harvard's vacation week.
Otherwise, the rioting would have been unbearable. 

Cambridge Area Economics and Computation Day 2013

I was asked to advertise the upcoming Second Cambridge Area Economics and Computation Day (CAEC'13);
information is available at http://caec.seas.harvard.edu/

It's being co-chaired by Turing-award winner Silvio Micali and Harvard's own Yiling Chen.

The data/location is

Friday, April 26, 2013
Singleton Auditorium (46-3002)
Brain and Cognitive Sciences / McGovern Building, MIT
43 Vassar Street, Cambridge, MA 02139

Registration is free, but you have to register in advance.

Here's the call:

------------------------------
Call For Participation

A lot of research and business activity in the Cambridge/Boston area is engaged in economic and computational questions in regard to understanding and developing the economics of Internet activity. Examples of topics of interest include theoretical, modeling, algorithmic, and empirical work on electronic commerce, networked behavior, and social networks.
One of the main purposes of CAEC is to encourage collaboration between local researchers. Significant emphasis will be placed on a poster session and short talks. The overall structure of the day will involve four longer talks, by Daron Acemoglu, Yiling Chen, Matthew Jackson, and Silvio Micali, with a short talks session and a poster session over lunch, along with brief poster announcements.
Submissions

For short talks and posters, send an email to caec13@seas.harvard.edu by Thursday April 11, 2013, including a brief description of your work, along with an indication of a preference for the work to be presented as a short talk or a poster, or be considered for both. We will select a small number of short talks and put together a poster session.
Decisions about the program will be made by Monday April 15, 2013.
The suggested format for a short talk is (a) description of the problem, (b) statement of results, and (c) discussion of open research directions. There will be no time for setting up individual laptops for the short-talk session, instead we will have all presentations preloaded on a computer in the auditorium.
Registration

This event is free to participants, but PLEASE register by Monday April 22.
Breakfast and lunch will be provided for the event. There will be no cost to participants

Looking forward to seeing you there,
CAEC Steering Committee
Yiling Chen, Silvio Micali, Costis Daskalakis, Andrew Lo, and David Parkes 

Update: Andrew Auernheimer Watch

Well, this is going to give me nightmares for a while.

TechNewsWorld:

"Andrew Auernheimer, a hacker known as "Weev," was sentenced Monday to 41 months in prison for obtaining the personal data of more than 100,000 iPad owners from AT&T's publicly accessible website and sending the information to the media. The ruling immediately sparked an outcry from a digital rights group that claims the punishment does not fit the crime."

Wired:

Auernheimer and Spitler discovered that the site would leak e-mail addresses to anyone who provided it with a ICC-ID. So the two wrote a script – which they dubbed the “iPad 3G Account Slurper” — to mimic the behavior of numerous iPads contacting the web site in order to harvest the e-mail addresses of iPad users.
...
The two contacted the Gawker website to report the hole...
On Monday, following the announcement of his sentence, the Electronic Frontier Foundation announced that it had joined Auernheimer’s appellate team.

Slate:

"This is the third big CFAA-related case I’ve covered lately, the other two being those of Internet activist Aaron Swartz and Reuters deputy social media editor Matthew Keys. While the specifics of the charges in each case differ, all three illustrate the unfortunate plasticity of the CFAA, and how it can be shaped and contorted to cover almost any computing-related actions. (Did you fill out an NCAA bracket from your work computer today? Congratulations! Depending on your office’s computer use policies, you may have violated the CFAA!)"

Salon:

Heading into his sentencing hearing, “Weev” reportedly proclaimed, “I’m going to jail for doing arithmetic!” And in an earlier Twitter direct message conversation, the hacker told me what he believes to be the issues at stake in his case. He explained that the AT&T data he accessed was already “published” — the telecom company has admitted as much. “The government asserted that after the fact, they can declare a given access to data anyone makes public ‘unauthorized’ and have you thrown in prison,” he wrote.
...
As well as 41 months in jail, “Weev” has been sentenced to an added three years’ probation and must pay more than $73,000 in restitution to AT&T.
...
Auernheimer will appeal the federal court’s decision. On Monday, the Electronic Frontier Foundation announced that its attorneys would join his legal team. “Weev is facing more than three years in prison because he pointed out that a company failed to protect its users’ data, even though his actions didn’t harm anyone,” EFF senior staff attorney Marcia Hofmann said. “The punishments for computer crimes are seriously off-kilter, and Congress needs to fix them.”

But I Haven't Thought of You Lately At All....

I realize the times they-are-a-changing, and so maybe I shouldn't find this unusual, but...

Kristen Bell and Rob Thomas put up a Kickstarter campaign to raise 2 million to make a Veronica Mars movie.*  They gave the project 30 days to raise the money.

Done, in less than 24 hours. 

There have got to be huge lessons for e-commerce and marketing there.  I'm still trying to figure out what they are.  Maybe it's also just because I watched Amanda Palmer's TED talk recently, but the idea that you can now just go to the world and say, "Help support this project, that you will love" and it can happen, at a scale that I don't think was possible even ten years ago, feels very powerful.

Or perhaps I'm just happy that they're going to make a movie.  

* The first season of Veronica Mars remains one of the best things ever on television.  It's not just me saying that -- it was Joss Whedon and Kevin Smith.  Go buy the DVDs or something if you don't believe me.

 

Turing Award : Goldwasser and Micali

Got in the office this morning and heard about the latest Turing Award:  Congrats to Shafi Goldwasser and Silvio Micali!  (Press release.) 

A Second Life for our Groupon Paper

Groupon has been in the news lately -- something about their CEO leaving, I hear.  And Giorgos Zervas has been out giving talks.  (He's a great speaker.  You should invite him to your next related workshop or conference.)  The combination of these events seems to have given our Groupon work ([Byers Mitzenmacher Zervas] the newer arXiv paper, the older arXiv paper) a new life in the press.  I've seen it up on Forbes (by way of Rajiv Sethi's blog) and the Freakonomics blog, from which is seems to be being re-distributed through the Internet in the standard way.  Amusingly, the Freakonomics blog refers to it as a "new" paper (it's not), and nobody ever spells Giorgos's name right (this time, it's Servas instead of Zervas).

Since my name has been appearing in the press the past several days for less interesting reasons, it was nice to see it in the "news" for actual work. 

The Press

Harvard's name, obviously, still sells newspapers.  The "e-mailgate" scandal of the past few days has been appearing everywhere.  I was contacted multiple times from various news organizations over the weekend and yesterday -- the most contact from the press I've ever had.

I've chosen not to talk to them, not because I'm against the press, or because I'm naturally shy (I write a blog, after all), but because I don't feel I have anything much to say, other than what I'm saying here on the blog.  I don't have any additional facts other than what I'm getting from publicly available information.  I suppose the press is looking for my opinion, or more realistically some good quotes, but I'd rather not work through my opinions on this issue over the phone with a reporter.   

However, I guess I am "on the record":  reporters have quoted the blog.  While I'm not entirely comfortable with that, I suppose that's the way it is.  It's somewhat disappointing when you have to explain to your mother that yes, your name was in the New York Times, and no, you didn't do anything important.  

My first blog post on this was part of the narrative that the faculty was critical of the administration.  I noticed my second post has been interpreted that I've been "mollified" (a term used in at least one article) by the administration's explanation, which I do not think is accurate.  I'm glad the administration explained what happened from its point of view, and that it offered an apology (even if many interpret it as a half-hearted one);  I think the Harvard community was owed the explanation, and the Resident Deans were owed an apology. I acknowledge that the administration did a good thing to present that statement.  But I still say (quite clearly in the 2nd post) that I think the administration made a mistake, and there's clearly resulting damage they will have to deal with.  I can only imagine the Resident Deans are especially angry -- I don't believe I've seen a formal statement acknowledging that they are "faculty", but some of the initial speculation that the administration didn't feel they had to follow the "faculty policy" for them would, I surmise, be very insulting.  I don't believe the administration's statement addressed this point, but perhaps it has been addressed privately.  I also believe there's lasting damage to the trust between administration and faculty.  Harry Lewis has said he'll move much of his e-mail to a private gmail account;  I suspect many other faculty will do the same.  I also worry that this has damaged the nature of the relationships between Resident Deans and students, as Resident Deans are meant to be a "go-to" point for students experiencing a variety of problems.  Both sides, I suspect, will feel more wary of what they say to each other, if they are concerned the administration might be watching.  Those feelings may not be warranted, and the administration has tried to make that case in discussing the targeted methods they used when looking at the e-mail;  that doesn't mean they those feelings won't be there. 

I don't expect this issue to just go away without further discussion, at the upcoming Faculty Council and FAS Faculty meeting.  Some people still have questions as to how this came to pass.  Larger scale, this fits into a narrative I've heard multiple times the last few days, about the "corporatization" of universities in general and Harvard in particular.  It's an issue that many faculty naturally feel very strongly about.  This event may galvanize some reflection or future action on that front.

So again, I don't think this is over.  But I think the form it takes from this point may be much less interesting for the press.

There's also more positive news on "the press" front, but it's worthy of it's own, separate post, which will be right up. 

Mike Smith Explains, Apologizes

Given the hubbub that arose this weekend over the issue of Harvard examining the e-mail of some of the Resident Deans, it's gratifying (if unsurprising) that this morning Dean of the Faculty of Arts and Sciences Mike Smith has released a statement, which explains the incident from the administration's point of view.

My high-level take -- this has been blown out of proportion by the media, but it's certainly an issue the administration and faculty should discuss and work out together, so there's a common understanding.  

Here's my summary (with commentary), but of course you should go the source.
1)  It was apparent that an e-mail labeled confidential has made it's way out to the press.  While the e-mail itself might not have contained especially sensitive information, the administration was concerned.  Who knew what else might have or would be leaked?  There was also concern that other specific confidential information had leaked to the Crimson.

Commentary:  The Ad Board member, who apparently forwarded a note containing advice on how Resident Deans might advise their students with regard to the Gov 1030 case, made an understandable error in judgment.  It's best not to forward mail labeled confidential, even if it seems unimportant.  If they had just rephrased the advice in their own words, perhaps this would have been avoided.  The administration's concern is also understandable, given the student privacy issues around Ad Board proceedings.

2)  The administration says they asked the Ad Board members about the forwarded email, but "No one cam forward", and they were told this might cause an investigation.

Commentary:  Sounds good.  This was something that wasn't clear or known (at least by me) based on previous reports.

3)  The administration decided to do a targeted e-mail search, looking specifically at the "Resident Dean" accounts (and not the "individual Harvard email accounts");  they did not look at the email content, but just looked at the subject lines to determine if the email in question had been forwarded. 

Commentary:  While I pleased with the care with which they did the search so as to avoid violating the privacy of the Resident Deans, I don't think this care offers an excuse for not following the policy of informing the Resident Deans of the search.  I would still say a search on their email had been performed and, from my understanding of the policy, they should have been notified.  This is something the faculty and administration can and should discuss further.  (In particular, should searches be required in the future, I do think the administration should be encouraged to follow a similar process to specifically target the search.)

4)  After the forwarding had been found, the administration determined it was an inadvertent error, and no further action was taken. 

Commentary: Based on what I know, I agree, and think the administration took the right action.

5)  The administration made the decision not to inform the other Resident Deans, in order to protect the privacy of this Resident Dean and "[allow] the students cases being handled by this Resident Dean to move forward expeditiously."

And now here's the key statement to me in the statement:

"We understand that others may see the situation differently, and we apologize if any Resident Deans feel our communication of the investigation was insufficient."   

Commentary:  In the original story I saw at boston.com, Sharon Howell, senior Resident Dean, said the following:

“They don’t seem to think they’ve done anything wrong,” she said. “[I told them], if you want to repair this with the resident deans, it would make sense to talk about why you thought this was the right thing at the time, and apologize for not notifying us after the fact.”

I feel that the administration has done this.

I've seen postings in other places, where people are suggesting that this case demonstrates some sort of moral failing, and that someone somewhere should be dismissed.  I disagree.  In my opinion, a Resident Dean made an understandable (and I would argue small) error in judgment in forwarding an email marked confidential.  The administration was rightly concerned.  In my opinion, the administration made an error in judgment by not treating the Resident Deans as faculty and strictly following the Harvard policy by informing them that a search was being done as part of an investigation into the matter.  I'm not clear if they feel they made an error in judgment, but they have apologized.

The faculty now have a chance to discuss with the administration why they felt this was an error in judgment and how they'd like to see similar situations handled in the future.  I expect and hope these conversations will happen.  But I don't think that's the sort of exciting stuff that somehow gets into the New York Times. 

Harvard Spies on E-mails

A strange offshoot of the Harvard cheating scandal -- a report in the Boston Globe that Harvard administrators decided it was OK to search through Resident Dean e-mails when some information marked confidential had appeared to have been leaked.

Just some "vocabulary" for non-Harvard people.  Resident Deans are people who live in the Harvard dorms (what we call "houses") who help administrate the dorms and work with students.  For example, one of their jobs is to serve on the Administrative Board ("Ad Board"), which, as I've talked about, handles disciplinary cases, including the now infamous Gov 1030 cheating scandal.

Short version of the story:  it was noted that a confidential e-mail of the Ad Board had apparently leaked out to the Crimson.  The e-mail was pretty innocuous, but of course one doesn't want confidential e-mails leaking about.  So someone in the Harvard administration decided a bright idea was to check the e-mail accounts of the Resident Deans without telling them to see if they had leaked it.  (Apparently, one had.  Success!)  

Now, since Professors are the uber-people in the university*, we have rules to protect our e-mails from being searched except in extreme circumstances (and even then with notice), as the article points out.  I found it online after a bit of searching.  The first paragraph is:

"The Faculty of Arts and Sciences (FAS) provides the members of its faculty with computers, access to a computer network and computing services for business purposes, and it is expected that these resources will be used in an appropriate and professional manner. The FAS considers faculty email messages and other electronic documents stored on Harvard-owned computers to be confidential, and will not access them, except in the following circumstances."

(I was amused when the article noted "That FAS policy was drafted in part because some professors feared that previous president Lawrence Summers was monitoring their correspondence."  Summers really was quite unpopular with many faculty, and while I can't recall what specifically had some professors concerned about whether the administration could read or was reading our e-mail, I hope some of my colleagues can remind me in the comments -- I do recall that concern being around.)

So it would seem that the administration violated its own policy.  What ground do they have to stand on?  It seems like the only question is, are Resident Deans "faculty" under the policy?  They generally hold lecturer positions within the University, but they are also generally not tenure or tenure-track.  But as far as I can tell right now, they're faculty under any reasonable definition the university gives.

(The FAS Handbook described Lecturers as follows:
"A lectureship is a short-term, non-tenure-track position that is held by individuals who serve as course heads for courses that would otherwise be taught by tenure-track or tenured faculty. Lecturers must hold a Ph.D. All lecturer appointments must be based in a department or degree committee."
Sounds like faculty to me....) 

I was pleased to see CS faculty members Harry Lewis and Greg Morrisett quoted in the article, with both of them being pretty unhappy to hear about this.  Greg's comment that "a lot of faculty are going to be 'pissed off'" rings true to me.  (I assume I won't have to, but if nobody else makes a big deal about it -- hard to believe -- I would plan to bring it up at the next FAS faculty meeting.)

Also, it just seems silly.  They could have/should have first asked the Resident Deans if any of them had messed up, and let them know that Harvard considered the leak of Ad Board related confidential information a sufficiently big issue that they planned to search their e-mail if necessary.  My reading is the FAS policy would have allowed for that, according the following paragraph:

"Second, in extraordinary circumstances such as legal proceedings and internal Harvard investigations, faculty records may be accessed and copied by the administration. Such review requires the approval of the Dean of the FAS and the Office of the General Counsel. The faculty member is entitled to prior written notice that his or her records will be reviewed, unless circumstances make prior notification impossible, in which case the faculty member will be notified at the earliest possible opportunity."

One might quibble as to whether the e-mail leaked in this case corresponds to an "extraordinary circumstance", but if the administration had followed this policy, it would have been hard to argue with.  Why didn't they do this?  We (or at least I) don't know.  Heck, it could be that they forgot about this policy.  There are so many pages of policy around, it's hard to keep track of them all, as I've annoyingly found while serving as Area Dean.  Or they did remember the policy, but actively decided that Resident Deans weren't "faculty".  Or, they just really didn't care.  Lots of possibilities.  But the idea that nobody had the common sense to say, "Whoa!  Isn't it bad precedent to go looking through people's e-mail without going through other options or letting them know?" is the kind of thing that make faculty think they need to push back or even rein in the administrative side of the university.

So I expect to hear more on this issue.  

* Or at least we like to think so.  Though we can tell that the administrators increasingly think that they're the uber-people, and this can make us very unhappy in some circumstances.  Like this one.  

 UPDATE:  As is often the case these days, Harry Lewis and I are blogging in parallel on Harvard matters.  His insightful thoughts on this situation can be found here.  

Rankings Don't Matter (But)

Back when I started at Harvard, people would literally say things to me like, "I didn't know Harvard had computer science."

Now I could just point such people here.  

Discussing STOC 2013 PC with Joan Feigenbaum

Joan Feigenbaum is the Program Committee Chair for STOC 2013, where papers decisions were recently announced;  I served as part of the Executive Committee.  Joan did an excellent job running the entire process, and experimented with a "two-tiered" PC.  We agreed that it would be interesting to talk about her experience on the blog, and she agreed to answer some questions I posed.  We hope you'll find the discussion interesting.

1.  You're now completing your stint as Program Committee Chair for STOC 2013.  How do you think the program looks? 
I think it looks great.  We had roughly 20% more submissions than last year, and many of them were excellent -- an embarrassment of riches.  Once we decided to stick with the recent STOC practice of a three-day program with two parallel tracks of talks, we were faced with the usual problem for STOC PCs, namely having to reject many clearly acceptable submissions.  I guess that's a much better problem to have than an insufficient number of clearly acceptable submissions, but I still have reservations about this approach to conferences.  (There's more on that in my answer to questions 2 and 5 below.)

2. You tried a number of new things this year -- a "two-tiered" PC being the most notable.  How do you think it worked?  Where do you think it improved things, and where did it not work as you might have hoped?
When Lance Fortnow, SIGACT Past Chair, asked me to be the Program Chair for STOC 2013, he strongly encouraged me to "experiment" and, in particular, strongly encouraged me to try a two-tiered PC.  I agreed to do so, but it was a strange "experiment" in that it was not clear to me (or to anyone, for that matter) what problem a two-tiered PC might solve.  There was no hypothesis to test, and the whole exercise wasn't a controlled experiment in any well defined sense.  Nonetheless, I was able to reverse engineer my way into some potential advantages of a two-tiered PC and hence some good reasons for trying it.
      Before I get into those reasons, however, I should state the primary conclusion that I drew from this experience: Given the extraordinarily high quantity and quality of STOC submissions, it's extremely easy to put together a good program, and any reasonable PC structure will do.  That is, assuming that you don't want to change the nature of the product (where the product is a three-day, two-track STOC that has a fairly but not ridiculously low acceptance rate), you have a lot of latitude in the program-committee process that you use to produce it.  There's nothing sacred about the "traditional," 20-person PC with one chair and no PC-authored submissions; there's nothing definitively wrong with it either.
      Now what did we try this year, and what were some of its potential advantages?  First of all, we briefly considered changing the product, e.g., by having three parallel sessions, but decided against it; we set out to put together a STOC program that was similar in quality and quantity to other recent STOC programs but to do so using a different process.  We had an Executive Committee (EC) of nine people (including me) and a Program Committee (PC) of 62 people.  PC members were allowed to submit, but EC members were not.  The job of the PC was to read the submissions in detail and write reviews, and the job of the EC was to oversee and coordinate the reviewing process.  For example, EC members reassigned submissions that HotCRP had assigned to inappropriate reviewers, looked for submissions that required extra scrutiny because they might have subtle technical flaws, and, most importantly, looked for pairs of submissions that were directly comparable and needed to have at least one reviewer in common.  In order to promote high-quality reviews (which I thought should be attainable, because each PC member had fewer submissions to review than he would have in a traditional PC), I put together a list of suggested review questions and regularly reminded PC members to flesh out, revise, and polish their reviews based on committee discussions.  We made accept/reject decisions about a hefty fraction of the submissions fairly early in the process, based on two reviews of each submission.  For the rest of the submissions, we got additional reviews or asked the original two reviewers to consider them in more detail or both; for each set of comparable submissions that survived the first cut, an EC member conducted an online "meeting" (using both email and HotCRP comments) of all of the reviewers of submissions in the set.
      One potential big advantage of this way of doing things over the traditional way is that PC service can be much less burdensome.  Each PC member can review far fewer submissions than he would for a traditional program committee and can also submit his own papers.  He can devote considerably more time and attention to each submission assigned to him and still wind up spending considerably less total time and effort than he would under the old system.  He's also less likely to have to review submissions that are outside of his area(s) of expertise, because there are many more PC members to choose from when finalizing assignments.  The hope is that almost everyone in the theory community will be willing to serve on a STOC PC when asked if the workload is manageable, that PC members will be more satisfied with the quality of their work if they can spend more time on each submission and don't have to review submissions outside of their area(s), and that authors will get higher quality reviews.
     A second potential advantage is that the managerial and oversight responsibilities can be shared by the entire EC and don't all fall on the chair.  In almost every traditional program committee I've served on (not just STOC committees), there has been a great deal of last-minute scrambling.  In particular, I've been in many face-to-face program-committee meetings at which we discovered that various pairs of papers needed to be compared but had been read by disjoint sets of reviewers.  That's not surprising, of course, when everyone (except the chair) had spent the previous few months trying to read the 60 submissions assigned to him and hence hadn't had a minute in which to at least skim all of the other submissions.  These relationships among submissions can be discovered early in the process if there are enough people whose job it is to look for them.  Having an EC that can facilitate many parallel, online "meetings" about disjoint sets of gray-area submissions is also a big win over a monolithic face-to-face program-committee meeting.  The latter inevitably requires each PC member to sit through long, tense discussions of submissions that he hasn't read and isn't interested in; our procedure enabled everyone to participate in the discussions to which he could really make a contribution -- and only those.
     I think that most of these hoped-for improvements actually materialized.  Certainly almost everyone whom I invited to serve on the PC said yes, and many said explicitly "OK, I'll do it because the workload looks as though it won't be crushing," or "I really appreciate the opportunity to submit papers!"  Similarly, we had no last-minute scrambling, and I attribute that to the oversight work done by the EC.  All of the potential technical flaws in submissions that we discovered were discovered early in the process and resolved one way or the other (sometimes with the help of outside experts); similarly, all of the pairs of submissions that, by the end, we thought should be compared were assigned to common reviewers early in the process.
      Unfortunately, the effect of the lower workload on quality of reviews was disappointing.  There was some improvement over the reviews produced by traditional STOC PCs but not as much as I had hoped for.

3. In my experience, our major PCs -- STOC and FOCS -- have small amounts of institutional memory and even smaller amounts of actual analysis of performance.  What data would you like to have to help evaluate whether the PC process went better this year?
For this year, I'd like to hear from PC members whether they did in fact spend less time overall but more time per submission than they have in the past on "traditional" PCs.  I'd also like to know whether they found the whole experience to be manageable and unstressful (if that's a word) enough to be willing to do it often, by which I mean significantly more often than they'd be willing to serve on traditional PCs.  Finally, I'd like to know whether the opportunity to submit papers was a factor in their willingness to serve and whether they found it awkward to review their fellow PC members' submissions.
      If future PC Chairs continue to experiment with the process or even with the product, as I suggest that they do in my answer to question 5 below, then I hope they'll capture their PC members' opinions of the experimental steps they take.

4. Are there things you did for the PC that you would change if you had to do it again?
Because the goals of this "experiment" were so amorphous, I and the rest of the EC members made up a great deal of the process as we went along.  If I were to run this committee process again, I would start by creating a detailed schedule, and I would distribute and explain it to the entire PC at the beginning of the review process.  I'd also lengthen the amount of time PC members had to write their first round of reviews (used to make the "first-cut" accept/reject decisions) by a week or two.  I'd also assign second-round reviewers at the beginning, rather than waiting as we did until after the first round of decisions had already been made; we wound up losing a fair amount of time while we figured out whom to ask for additional reviews, and I suspect that many PC members wound up losing interest during this down time.  So each submission would still receive just two reviews in the first round, but third (and perhaps fourth) reviewers would have their assignments and be ready to start immediately on all submissions on which early decisions weren't made.

5. Are there things you would strongly recommend to future PC chairs?
I hope that the theory community as a whole will consider fundamental changes to the form and function of STOC.  As I said in my answer to question 2, if we want to continue producing the same type of product (a three-day, two-track conference with an acceptance rate somewhere between 25% and 30%), then there are many PC processes that would work well enough; each PC chair might as well choose the process that he or she thinks will be easiest for all concerned.  The more interesting question is whether we want to change the product.  Do we want more parallel sessions, no parallel sessions, different numbers of parallel sessions on different days, more invited talks, more papers but the same number of talks (which could be achieved by having some papers presented only in poster sessions), or something even more radical?  What do we want the goals of STOC to be, and how should we arrange the program to achieve our goals?
     The community should discuss these and other options.  We should elect SIGACT officers who support experimentation and empower future PC Chairs to try fundamentally new things.
      More specifically, I recommend that future PC chairs include, as we did, a subcommittee whose job it is to oversee the reviewing process rather than actually to review submissions; in our case, this oversight function was the responsibility of the executive "tier," but there might be other ways to do it.  As I said in my answer to question 2, giving oversight and management responsibility to more people than just the PC Chair really helped in uncovering problems early and in making sure that related submissions were compared early.
      Finally, I'd of course recommend that future PC chairs not make the same mistakes I made -- see my answer to question 4.

6. In my experience, the theoretical computer science community is known for comparatively poor conference reviewing.  Having been PC chair, do you agree or disagree?  Do you think the two-tiered structure help make for better reviews? Do you have any thoughts on how to make reviewing better in the future?
In my experience, reviews on submissions to theory conferences range enormously in quality.  The worst consist of just a few tossed-off remarks and the best of very clear, well thought out, constructive criticism.  As I said in my answer to question 2, I had hoped that the two-tiered PC and its concomitant lighter reviewing load (together with my suggested review questions and regular prodding) would lead to a marked improvement in the quality of reviews, but we got only a small improvement.  I was extremely disappointed.  Frankly, I don't know what the theory community can do about review quality.  Maybe we should start by discussing it frankly and finding out whether people really think it's a problem.  If most people don't see it as a serious problem, then perhaps we don't have to do anything.

7. As you know, I'm a big fan of HotCRP.  How did you like it?
I've used three web-based conference-management systems: HotCRP, EasyChair, and Shai Halevi's system (the name of which I don't remember).  In my experience, they're all reasonable and certainly capable of getting the job done, but none of them is great; HotCRP is the best, but not by a wide margin.  Part of my problem was that I had unrealistic expectations going in.  I'd been told that HotCRP was almost infinitely flexible and configurable, and I thought that it would be easy to set things up exactly as I wanted them; that turned out not to be true.  On the other hand, if you use HotCRP exactly as it was designed to be used, it works quite well.  I have the feeling that it is a "system builder's system" in that it's very powerful and very efficient but not all that easy on users; the UI is not great.  Anyway, you and I do agree on one thing: HotCRP's "tagging" feature is amazing; PCs of all shapes and sizes should make heavy use of it.

ICALP formatting

Given the loud outcry regarding the STOC 2013 formatting, which gave you 10 double-column pages to work with (at the cost of, you know, having to turn your paper into double-column format), I though I'd again express my annual dismay at the format for ICALP submission.  Twelve LNCS pages is simply not enough space to present anything interesting at a suitable level of detail.  I'm tempted as always to turn in a 1 page paper, that says "If the 1 paragraph abstract sounds interesting, here's the arxiv link to something you can read."  Why they haven't pushed LNCS to allow at least 14 pages remains a mystery to me. 

Back to formatting.

Online Censorship Day and Other Links

1)  Sharon Goldberg and Nick Feamster asked me to announce the following:

In the tradition of CAEC, NYCE, and etc, we are holding a "Day" on online censorship at BU on March 8, with speakers from technology, law and public policy.  We're currently soliciting abstracts for short talks and posters (due Feb 21).  Info is here:

http://www.bu.edu/cs/bfoc/

2)  The Crimson has a nice article on CS at Harvard, leading with

The computer science concentration has nearly doubled in size in the last two years and continues to drive growth in Harvard’s School of Engineering and Applied Sciences, according to new data released by the SEAS Communications Office.

3)  I wanted to point to this essay by Don Rosa.  Don Rosa is well-known as the writer and illustrator for many of the tales of Scrooge McDuck, which I didn't read as a kid but have enjoyed with my kids as an adult.  (I'd recommend the Life and Times of Scrooge McDuck, but there doesn't appear to be an affordable version available on Amazon right now.)  The essay is a poignant explanation of why he stopped, which I expect might resonate with many people, including those who have never read a comic. 

Daily Show

Anyone else watching Jon Stewart making fun of Harvard w/regard to the "cheating scandal".

[I need the exact wording for the punch line -- "Open Internet?  Is this Harvard or the University of Phoenix?"]

Zachary Quinto and Cherry Jones are in Town...

Harvard had a special faculty meet-the-director-deal thing for a preview of The Glass Menagerie, playing the next few weeks at the American Repertory Theater, that my wife and I went out to tonight.  Cherry Jones and Zachary Quinto are the leads.  It was excellent, though, of course, totally depressing in that Tennessee Williams play way.  Shockingly (to me), there appear to be tickets available.  If you're in the Boston area, I'd highly recommend making an evening out of it.  Enough so that I thought to blog about it.

Ad Board Update

We've finally got an update on the Government 1310 situation.  As reported by the Crimson, FAS Dean Mike Smith sent out an email Friday, where he wrote that

“somewhat more than half” of cases heard by the College’s Administrative Board last fall resulted in forced withdrawals

and many of the other half resulted in disciplinary probation.  While this includes more than Gov 1310, given the size of the case, that probably represents the bulk of the withdrawals.

On the positive side, the university tried to limit any financial damage to students given the long time frame required to reach decisions, rolling it back for tuition purposes as though they had to withdraw September 30.  It seems like they could have decided and announced that previously, but at least they did it.

For better or worse, I suspect we won't be getting substantially more details given the (appropriate) confidentiality with which these cases are handled.  I would like there to be some way that more could come out of this, though it appears that will be indirect.  A fairly recently-developed Committee on Academic Integrity (which does pre-date the Gov 1310 situation) will be making recommendations on issues such as whether Harvard should institute an honor code and how faculty should structure assessments.  I'm skeptical that these will get to the deeper issues -- what we mean by cheating (especially in the Internet age) and whether the faculty have a consistent and clear policy about it, what leads students to cheat, and what the role of the University is in developing morality in the student body.  At the same time, I'm sure these issues are much closer to the surface now than they have been in the past, and are discussed more amongst faculty and students, in unofficial settings.

Further update:  I highly recommend Harry Lewis's latest (and last?) post on the issue, and the discussion in Harvard Magazine, which includes the full text of Dean Smith's letter.  

Friday Ruminations

It's felt like a bad few weeks at Harvard.

Not that anything actually BAD has happened, like an inexplicable paper rejection or some interdepartmental fight or anything.  It's just that January is filled with time-sucking (or, really, just sucking) administrative work normally, and it's worse this year as I have more administrative duties. 

My weeks have been spent looking over faculty applications and graduate applications, and dealing with the paperwork and relevant meetings associated with such.  Handling multiple promotion cases.  Writing letters for students applying for internships or summer programs or whatever.  Preparing for my class this semester -- a process exacerbated my Harvard's fairly recent change of schedule which places many students away from campus from December finals until the day classes start, making it hard to organize the mostly undergraduate teaching assistants.  Handling papers as part of the STOC executive committee.  Reading some undergraduate admission folders.  Chairing a grant panel (for a friendly foreign country).  Writing letters for colleagues outside Harvard going through promotion cases.  (You're welcome.)  Dealing with the myriad issues of the other CS faculty that pass through me while I'm Area Dean.  It's rare that I've had the 20 minutes to think about research, talk to my collaborators, or work out things with my graduate students. 

Individually, there's nothing bad about any of these tasks.  They're part of the job.  But packed together, so I feel like I'm on an administrative treadmill, it's wearing me out.  If it's optional in February, I'm saying no.  (That means you, ISIT papers people have asked me to review.) 

On a more positive note, I was at a new concentrator event, and ended up talking for a while with four or five women who plan to major in CS at Harvard, most of whom are currently taking my class.  I'm happy that we're seeing many, many more women in CS at Harvard;  my only disappointment is that it hasn't been that way for so long. 

CS 124 is holding steady at about 100-110 students this year, maybe a little smaller than last year, but at the level of noise.  We've got four CS classes over 100 people this semester from the looks of things.  (To calibrate, that's a lot for us spoiled Ivy League faculty.)  Overall CS enrollments keep on growing.    

Finally, an amusing note, in Harvard's Courses of Instructions I'm listed as the teacher next year for CS 221, our graduate complexity course.  There always seem to be many bugs in the data for course listings, but this is particularly funny, as I'm planning to be on sabbatical next year, and I've never taught (or had it suggested that I teach) 221.  Someone transposed something somewhere.

On My Drive in This Morning...

It would, of course, be completely inappropriate for me to write that if you're interested in illegal prescription drugs, you should go talk to Stefan Savage of UCSD.  But it's more appropriate for me to give a shout-out to him for his recent appearance on Planet Money's podcast, in Episode 430:  Black Market Pharmacies and the Spam Empire Behind Them, which I listened to on my way into work this morning.  It's well worth listening to.  The podcast's take summarized (which matches my experience with other non-drug online advertising based businesses, and I think I'm summarizing Stefan correctly) -- it's actually a pretty boring business.  Online pharmacies are just trying to sell something, get their cut, and spam mail is their effective way of advertising.  (Since selling prescription drugs without a prescription in the US is illegal, they can't exactly advertise on TV.)  Stefan mentions in the podcast that in cases he's examined, they don't appear to be trying to send you placebos or bad product;  they're just making their margin, like other retail businesses. 

Maybe Stefan will see this and offer some pointers to research in the comments.  In any case, I enjoyed listening to his insights and smooth-sounding voice on the drive. 

Auernheimer Speaks

Auernheimer -- who as I've discussed on this blog was convicted of a felony by accessing AT&T servers -- put out a statement yesterday. 

Here Comes Another One

And yet another security story -- this one titled find a bug, get expelled or something close to that in various places. I'm going to have to find out where I send an opinionated letter to Dawson college.  

Also, if you haven't been reading it, I'd really recommend reading the last week or so of posts on Harry Lewis's blog, which goes into a lot of depth on issues related to the Aaron Swartz's case, university governance and culture, and the Harvard cheating case.  

Aaron Swartz : Links

If you haven't done so already, today is a good day to reflect upon the life of Aaron Swartz. 

If you haven't heard of him or need background, you can always start with his Wikipedia page. 

After that, I'd recommend reading the words of Cory Doctorow, Lawrence Lessig, and Glenn Greenwald. 

Finally, it's worth reading the family's statement.

I am finding it disturbing that this is my second post involving government prosecution this year.  (Here was the first.)  This seems like it may be an important ongoing concern, although given the setting, a topic for another day. 

Government 1310 -- What's New?

So, as many of you may remember, Harvard had a rather embarrassing cheating scandal flare up at the start of the academic year, involving over 100 students.  To be clear, that's the number apparently involved in investigations;  it's not the number punished.  That's my point here -- we don't know how many were found to have cheated, or, really, much other information. 

A bunch of Crimson articles can be found here.  There don't seem to be any after the beginning of October.  We originally heard that the students would have their case outcomes determined by November.  So, where do we stand?

I might be missing something, but I can't find any updates on the situation.  Please inform me if there's more I don't know about.  But it seems to me that the faculty -- and, arguably, the public at large -- merit some further information.  If the cases are still ongoing, a brief note saying that, along with a statement that the lessons learned will be discussed at an appropriate time, would be fine.  But honestly, I'm disappointed and disturbed (albeit not surprised) by the lack of information.

I understand that this can't be a popular topic in the administrative circles.  But at the time when the news broke there was a great deal of talk about how the incident should open the door to further discussions about cheating and pressure on students.  And certainly after the fact there should be greater understanding of what happened in this specific class and how we might prevent it in the future.  It seems to me there are basic things the faculty should know -- like whether it turned out that 10 or fewer students were required to withdraw, or more than 50.  And ideally, we should know it sooner rather than later.  In fact, it seems like the beginning of the new semester is just the right time to get this information out, as faculty share with students their expectations regarding collaborative work for this set of classes.

Perhaps the powers that be are just waiting for the semester to start.  But really, I think we're due an update, with some basic analysis of what ended up happening and how we as a community should think about responding to it.  I wonder when (if?) we'll see it.

Any Good Voronoi Code Out There?

Help!

I've got a wacky idea I'd like to explore (pseudo-preliminary-pre-research stage) which will require some code, namely for Voronoi diagrams.  What I'd like seems like it should be available.  I think I want the following:

1)  I input a list of points -- 2-D is fine, but hey, if the code can handle 3-D, more time-wasting fun.
1a) Update: I suppose what I really want is for code that works on the "2-D torus" -- i.e say on the unit square [0,1]^2 where the boundaries wrap around, so that there's symmetry.  That would be ideal, but from what I understand "torus" versions of the algorithms are harder to find, so maybe I'll just have to deal with regular 2-D and truncate somehow.
2)  For the output, all I really want is the area of each cell corresponding to each point.  Sure, if more information is available -- things like number of sides of the cell, etc. -- again, more time-wasting fun for me.  But for now cell area seems most interesting.  (I don't need pretty pictures.) 
3)  Now, the painful part -- I expect to be doing a lot of incremental inserting and deleting of points.  So I'd like to have code that's very fast if say I delete a point from my list and insert a new point elsewhere.  The code I've seen available seems to (if I'm understanding right) just implement the algorithms where you have a list of points.  Some of them use incremental insertion and can therefore probably be modified easily to handle point insertions, but not point deletions.  Somehow I think dealing with point sets of thousands or more and re-computing from scratch when I delete a point seems like it will be way too slow for my explorations.  I realize handling deletions is harder, but that there exist algorithms for it, so I was surprised I can't easily find relevant code.  But maybe I'm just looking at the wrong place.


I suppose whatever language the code is I can figure out how to use/wrap/rewrite it to my needs, so I shouldn't quibble about those sorts of issues.

Strangely, I can't seem to find anything that meets these needs.  Feel free to set me straight via comments or mail.  Or, if it seems to be something I'll need to implement myself, feel free to point me to the most helpful relevant papers.
  

Security, Disclosure, Legality

I guess I'm late to this news, but I stumbled across the case of Andrew Auernheimer, who was convicted of one count of identity fraud and one count of conspiracy to access a computer without authorization, for posting to Gawker that AT&T had a data leak that allowed anyone to get information about a set of AT&T iPad users. A description of what occurred can be found for example in this Wired article.  I also recommend this opinion on the matter by Matt Blaze, or this take by Ed Felten.

This case hit home for me because, as you may recall, last year we had an entirely similar situation with Yelp.  We found that they were accidentally leaking personal user information.  We collected data to back our claims if needed, brought it to them, and they fixed it.  Moreover, when we told them this leak should be made public (after they had fixed it), they agreed to do so;  their blog post on the issue remains up.  As I mentioned at the time, it was an exemplary experience.  Now I feel even more so.

Did we handle it differently, by contacting the vendor first?  Yes.  And perhaps these two situations exemplify some of the differences between what some people call full disclosure vs. responsible disclosure.   But it's very unclear to me why what Mr. Auernheimer did -- finding a flaw and disclosing it in the manner he did -- would be considered illegal.  Or, perhaps more to the point, it's not clear to me at this point what the difference is between what he did and what we did, which worries me, because as far as I can see, we should not have been anywhere close to any legal line in how we dealt with a found data leakage.

Certainly we thought our responsible disclosure approach -- contacting Yelp -- increased the likelihood of good will and a good outcome.  And, in retrospect, we may have been depending on our status as university researchers.  A legal action against us would have led a lot of negative press for Yelp (I think), and we'd have a lot of support from the academic community.  I should emphasize, though, that I'm not clear that we would have gotten much help from our universities. I contacted Harvard legal, and they were very hands-off.  Examples of the wording in their response to us. (Note, this was going through another layer, hence the 3rd person "the researchers" wording -- it's not just legalese).

If the researchers move ahead to disclose this publicly, as they intend to do, they should understand that the discovery and announcement is something for which they are responsible in their individual capacities (and should not be held out as an activity done by or on behalf of Harvard).

If there is some liability that results from the discovery or their announcement of it, the researchers should understand that they could not look to Harvard to cover that liability.

There are, as I’m sure you know, laws that prohibit certain kinds of hacking. It’s important for the researchers to be very comfortable that they were not engaged in any activity that could be construed as posing under another name, unauthorized breaking into a site, etc.

In the end, I think we were depending on common sense -- we found a leak, we aimed to get it fixed, we wanted it announced afterwards, for the obvious motivations -- credit, and protecting others.  Auernheimer didn't go to AT&T first, but what he did does not seem completely outside the realm of common sense to me.  (I suppose this is the heart of the full disclosure vs. responsible disclosure debate.)  So how as researchers do we protect ourselves from felony charges?  How as a practical matter do we improve computer security in this legal environment, or how can we change the legal environment to improve computer security while maintaining researchers' rights?

Auernheimer is due to be sentenced in February, although the articles suggest he will appeal his case.

No Stress

Greg Morrisett points me to this bit of silliness to start my morning:

University professors have a lot less stress than most of us. Unless they teach summer school, they are off between May and September and they enjoy long breaks during the school year, including a month over Christmas and New Year’s and another chunk of time in the spring. Even when school is in session they don’t spend too many hours in the classroom. For tenure-track professors, there is some pressure to publish books and articles, but deadlines are few. Working conditions tend to be cozy and civilized and there are minimal travel demands, except perhaps a non-mandatory conference or two. As for compensation, according to the Bureau of Labor Statistics, the median salary for professors is $62,000, not a huge amount of money but enough to live on, especially in a university town.

Generally, I love my job, and the great flexibility that comes with it.  And I do think it's less stressful than many other careers (at least, post-tenure, and in my mind even pre-tenure as well).  So the topic sentence is one that is hard for me to argue with.  But really, the description in the rest of the paragraph is so far from reality, it makes me giggle.  And I imagine the stress levels are significantly higher for professors outside of CS and the Ivy League -- for example, I make significantly more than $62,000, but I think that the way the author blithely ignores that making "enough to live on" may indeed be stressful is just absurd. 

Right now, of course, is actually a stressful time of the year, especially as I have to plan for next semester's class.  Pre-enrollment numbers are at about 129, suggesting something like a 5-10% rise from last year.  I don't have all my TAs in place, I have to revise the schedule/first few lectures to take into account changes in the courses before mine, and I have other administrative duties sucking up time before classes begin. 

But yes, I'm well aware I'm under much less stress than my college roommate the cardiac surgeon.

Answers for Assignments?

One of the smarter students I've known at Harvard, who has been a Teaching Assistant for me the last two years (and who I'm hoping will be back again this year), recently made the following argument to me, encouraging me to hand out written answer keys:

There are two approaches to giving quality feedback on student work: writing good comments for each student, which is O(N) for N students, and releasing answers to the pset problems, which is close to O(1). In classes that release pset answers, TF comment-writing decreases to almost nothing. We tried, last year, to implement an alternative O(1) solution, the "answer review sections" that I ran for each pset. I think that students who had been confused on the pset had trouble following these sections, and I don't think that they were nearly as effective as written solutions.

Here he's cleverly played a novel argument:  I should be providing answers not because it helps the students, but because it helps the teaching assistants, who are woefully overworked.  He knows I agree on this last point.  He also knows that I'm unsympathetic to the argument that it helps students to be given written solutions.

(Parenthetically:  Since this comes up often, I feel it necessary to be clear that it's not that I'm unsympathetic to students who have trouble on my apparently very difficult homework assignments;  it's just that I don't feel that handing out written solutions is the right response.  First, by what I consider necessity, I re-use problems, and experience shows that, given opportunity, even students who you would not imagine would copy old solutions run into situations where they believe they need to copy old solutions, which generally leads them to getting kicked out for a year at Harvard.  I don't like having to turn in students and then seeing them get kicked out for a year.  Second, even if you feel that cheating-prevention is not a suitable reason not to hand out assignment solutions, I'm not a big believer that written answer sheets help students learn better than other methods, such as getting more individual feedback and working out the problems afterwards from the assignments with TAs or others.  Or, if you want to see worked-out examples, buy one of the recommended textbooks and read it as well.  The fact that so many students fail to take advantage of opportunities to obtain and/or work through answers after the fact in the absence of written answers being handed out remains troubling to me.

Maybe I should just use MOOC techniques and have students turn in numerical solutions electronically that can be script-corrected.  And videotape my lectures and just replay them each year so I can stop showing up.)

This year, however, I'm entertaining his proposal... primarily because it's possibly my last year teaching the undergrad algorithms class for some time.  (With any luck, I'm on sabbatical next year -- and I'm likely to be passing the course on, after what will be the 15th year in a row teaching it, to one of our newer faculty.)  If someone else is teaching it, the calculus changes from my perspective.  (Though I suppose I should check that the incoming faculty are OK with the idea.)

What's your take?  It seems like an interesting way to change things up.

Put This On My List...

Put this on my list of papers I wish I had written: Manipulating Google Scholar Citations and Google Scholar Metrics: simple, easy and tempting. I think the title is sufficiently descriptive of the content, but the idea was they created a fake researcher and posted fake papers on a real university web site to inflate citation counts for some papers.  (Apparently, Google scholar is pretty "sticky";  even after the papers came down, the citation counts stayed up...)

Actually, I'm disappointed nobody in my graduate class thought to do something like this for a project.  I suppose it's hard to do as a class project, as it's a bit time-consuming (you don't know how long you'll have to wait to get noticed), and the outcome might have been nothing.  Or maybe I haven't clarified how much fraud can lead to interesting security projects!