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!

STOC Goings-On

Joan has permitted/encouraged me to post on the STOC PC process this year.  So far, all seems to be running smoothly.

Despite pre-conference suggestions by some naysayers that the formatting rules would be a problem, it doesn't seem to have been, unsurprisingly confirming that STOC submitters can in fact (with high probability) follow basic directions.

The hardest part, I think, has been the assignment process.  This always seems to be the hardest part on the PC end.  Having a large committee both helps and hurts -- more flexibility, but more individuals to deal with.  In particular, some people didn't seem to enter their paper preferences in a timely fashion, causing issues downstream.   Joan has been handling assignment issues as they arise, and I don't expect any significant problems in the end.

As usual, I'm thrilled to be using HotCRP over the alternatives.  I'm by no means an expert in HotCRP usage - I don't go around throwing down searches using Boolean expressions, or that check what the Overall Merit score fields are.  Still, nice to know that they're there.  I'm just thrilled that I can easily get the key overall view on my assigned papers, at a glance seeing how many reviews are in and the scores for everything.  Also, being able to tag papers in arbitrary ways just seems like key functionality.

First-round reviews are trickling in.  To all of you on the PC, thank you - and please get those reviews in!  It's actually helpful to us if you submit reviews as you do them as opposed to waiting to put them all in the system in bulk at the deadline, so please post them as you can.

Assessing Computer Scientists

My colleague and frequent co-author John Byers knows that I can spend up to several hours a day actively worrying about my ranking as a computer scientist.  While the automated daily Google Scholar updates (any new citations today?) are helpful, it's not always clear how I should interpret them. So John was happy to direct me to a new paper, Assessing Computer Scientists Using Citation Data, to help me and other ranking-obsessed individuals find their place in the world.

The methodology itself is actually quite interesting.  The first question is what version of the h-index do you want to use?  In particular, what external information do you use to judge which version of the h-index appears most accurate?  The method used here is to assume that department rankings accurately represent the quality of the faculty within the departments, and use a regression between the reputation of departments and the mean citation score of the faculty to help determine which versions of the h-index appear most accurate for assessment purposes.  There are several other factors accounted for in the methodology, such as a prediction model for the probability a computer scientist works at a department depending on their quality "mismatch", and how to take into account the thing like the field and years-since-PhD of individual researchers.  (Theory papers as a group obtain much fewer citations on average;  security and cryptography papers, much more.)  The latter allows one to come up with variations of the h-index score that are field- and age-adjusted to individual researchers.  That is, the paper provides a systematic approach that attempts to correct for some of the known weaknesses of h-index scores.  This sort of analysis is common in econometric papers, and is the same general type of analysis we did in our Groupon paper a while back.

I'm well aware that many people object to this type of ranking of individuals, some based on arguments of principle (this isn't how scientific research should be judged) and some based on technical arguments (these approaches are fundamentally flawed).  This work doesn't really try to address the first type of argument, but arguably it goes a fair way toward addressing various technical concerns by showing a suitable application of econometric techniques.  How well does it do?  You'll have to look at the tables in the paper and decide for yourself.    

I generally find these types of measurements useful, with the understanding that they're imperfect.  (When asked to write a promotion letter for someone, for instance, I do examine citation counts.)  To the extent that they become "more perfect", the implication seems to me that they will become the standard first-order approximation of quality.  I don't see how such an outcome could reasonably be avoided.  One argument is that it shouldn't, because it's a useful guide to performance;  if certain people don't perform well in relative terms under that metric, but should be thought of as exceptions to the first-order rule, then exceptional arguments (in letters and such) can be made when needed.  But then not everyone can or will be an exception.

Posts from FOCS (part 5)

[Again, edited by Justin Thaler, who organized all this.  The following was written by Michael Forbes of MIT.]


Title: Higher Cell Probe Lower Bounds for Evaluating Polynomials
Author: Kasper Green Larsen

Larsen gave a very understandable talk about data structure lower bounds, where he managed to survey the two relevant prior techniques and introduce his new technique. The lower bounds he discusses are in Yao's cell-probe model. On a basic level, this model is to data structures as communication complexity is to algorithmic complexity. That is, the cell-probe model (and communication complexity) are really only concerned with the ability of a data structure (or algorithm) to move information around. These models ignore computational factors. This makes their results (as lower bounds) hold generally (even when we do care about computation), and also allows us to actually derive results (since getting unconditional lower bounds on computation is hard, but lower bounds for information are possible).

Specifically, the cell-probe model thinks of a data structure as a random-access array of cells, each with a word of some fixed size. Each word can store some sum, or some sort of pointer to another cell. To allow pointers to be meaningful, we allow the word size to be at least log(n), and typically O(log(n)) is the word size considered, as this models real-life usage of numbers. A data structure then has two parts: (1) a preprocessing step for storing information into the cells, and (2) a method for probing these cells to support queries on the original information. In this model, we will only charge for (possibly adaptive) probes to cells. Once we have a cell's information, we can perform arbitrary computation on it to determine the next probe.

The cost of any conventional data structure (as designed, say, in the word RAM model) can only decrease in the cell-probe model, as we consider computation as free. Thus, any lower bounds in the cell-probe model will necessarily apply to any reasonable model for data structures one could consider.

The first technique (by Miltersen-Nisan-Safra-Wigderson) used to prove cell-probe lower bounds was based in communication complexity. As mentioned above, the data structure can be seen as divided: the cells storing the information, and the probes used to answer queries on this information. Given this division, it seems natural to divide these two parts between two players in a communication game, albeit one that is fairly asymmetric in the inputs the players have. That is, Alice has the query that we are trying to answer, and Bob has original information. They are tasked with outputting the answer to Alice's query on Bob's data. Notice that there are two trivial protocols: Alice could send her query to Bob, or Bob could send all of the original information to Alice. These are asymmetric, as typically Alice's query will have a very small description, while Bob has many bits of information.

A data structure can then be converted into a communication protocol as follows: Bob will alone construct the cells of the data structure, and Alice will send indices of the cells she wishes to probe. Bob will return the values of those cells, and Alice will generate the next probe, and so on, until the query can be answered. With this transformation, we can now apply the techniques of communication complexity to get the needed lower bounds.

While the above idea is a good one, it is not good enough for the regime that Larsen is considering. This regime is that of data structures that only have a poly(n) number of possible queries. A good example of this is where the original information is a set of n points in the two-dimensional grid [n]x[n], where each point has a weight at most n. The data structure seeks to return the sum of the weights of the points contained in a given geometric rectangle SxT, where S,T are intervals in [n]. There are n^4 possible rectangles and thus n^4 many queries. To compare, encoding the points takes O(n log(n)) bits. Clearly, in this regime a data structure using n^4 cells can answer queries in O(1) probes. The more interesting question is the time/space trade-off: how many probes are needed when we allow the data structure to only use as many bits as needed to describe the original information?

It turns out that in this regime, the above lower bound technique cannot give lower bounds better than a constant number of probes. This is provable, in the sense that we cannot prove good communication lower bounds because there are good upper bounds: the above trivial protocols are too efficient in this setting.

A second technique (by Patrascu-Thorup), more geared to this regime, uses again the above communication framework, but now gives Alice a harder problem. Alice is given d queries to answer on the single instance Bob holds. The reason this becomes interesting is because given a data structure for this problem, we can now develop relatively better communication protocols: Alice can run all d queries in parallel. Doing this naively will not gain much, but Patrascu-Thorup observed that in one round of Alice sending the indices of the cells she wishes to probe, the order of these cells is irrelevant, as Bob will simply return their contents anyways. Thus, Alice can then send fewer bits by encoding her messages appropriately. This approach turns out to yield lower bounds of the form lg(n)/lg(lg(n)), and cannot do better for the same reason as with the first technique: the trivial protocols are too efficient.

Finally, the technique Larsen introduces diverges from the above themes. Panigrahy-Talwar-Wieder introduces a cell-sampling technique for proving lower bounds, and Larsen takes this further. So far, he can only apply the idea to the polynomial evaluation problem. In this problem, we are given a degree n polynomial over a finite field of size n^2. We will support queries to the evaluation of this polynomial to any of the n^2 points of the field. As before, we can do this in O(1) probes if we have n^2 space, and rather we wish to study the question in the O(n * polylog(n)) space regime. Larsen shows a lower bound of log(n) probes in this regime, which notably is better than any of the previous techniques could hope to prove.

To prove this lower bound, consider any small probe data structure. If we subsample the cells of the data structure (delete any given cell independently and at random) then because any query can be answered by few probes, there will be many queries that can still be answered from the sub-sampled cells. As degree n polynomials can be recovered from any n+1 evaluations, if the polynomial evaluation data structure can still answer n+1 queries with the sub-sampled cells then this means that the sub-sampled cells contain at least as much information as the space of degree n polynomials. However, if the number of probes is small enough, then we can subsample so few cells that this will reach a contradiction, as the number of sub-sampled cells will be too small to recover an arbitrary degree n polynomial. Setting the parameters correctly then yields the lower bound.