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.

Computer Science Rhodes Scholar

A question we tend to get at Harvard is why students should come here to study computer science.  There are lots of reasons, of course, but one thing we like to emphasize it that it's possible to study computer science here but be a more "well-rounded" person than perhaps at some other places.

So I'm happy to provide the example of Aidan C. de B. Daly, a computer science concentrator who just won a Rhodes fellowship.  Congrats (to him and all the winners -- see their bios here.)

Harvard Financials

Harry Lewis has had several interesting posts this month over at his blog.  In particular, he discusses Harvard Magazine's recent analysis of Harvard's Annual Financial Report, which offers what I find to be a somewhat bleak picture of the last decade, followed by maybe some optimism for the current campaign.  Recommended reading for those who care about that sort of thing.  Overall, it paints a familiar picture of too many people being far too optimistic about economic conditions up through 2008, allowing and encouraging a grab by the central administration (in the form of a "strategic infrastructure fund") for big-ticket projects that have mostly fallen by the wayside.  Other failures include huge increases in debt and the still silly-seeming interest-rate swaps.  The end result has been a slow multi-year recovery, which (from my standpoint) seems competently managed (under the new administration), but unsurprisingly difficult -- we've had to give up a lot of opportunities to dig ourselves out of this hole, and outside economic conditions don't make it any easier.

Harvard continues to innovate, grow, and expand, even in this weakened state.  I hope that these new financial constraints will mean future plans will be more carefully and reasonably thought out than in the heyday of the early 2000's, even when improved financials offer us a little more breathing room.

Posts from FOCS (Part 4)

[Editor: In Part 4 of what now looks to be a 5- or 6-part series of reports from FOCS, second-year graduate student Ludwig Schmidt of MIT contributes a summary of the worksop on Randomized Numerical Linear Algebra from Saturday October 20.]

The workshop "Randomized Numerical Linear Algebra (RandNLA): Theory and Practice" was organized by Haim Avron, Christos Boutsidis and Petros Drineas. The website of the workshop contains the slides, abstracts and links to the speakers' websites: http://www.cs.rpi.edu/~drinep/RandNLA/ . Michael Mahoney has written a survey of the field: http://arxiv.org/abs/1104.5557 .

After a short introduction by Petros Drineas, Michael Mahoney gave a one-hour tutorial talk. The goal of RandNLA is to design better algorithms for numerical linear algebra by using randomization. Potential benefits include a better runtime (both in theory and in practice) and simpler algorithms that are easier to analyze and more amenable to parallel architectures. The tutorial talk focused on two core problems in numerical linear algebra that highlight the main ideas: low-rank approximation of matrices and least squares approximation for overdetermined systems.

Many algorithms in RandNLA follow a similar pattern: first, parts of the input matrix (rows, columns or entries) are sampled (or otherwise "sketched") in order to construct a smaller problem. This smaller problem is then solved with a traditional algorithm. If the sketch behaves similarly to the original matrix, the solution of the subproblem is close to the solution of the original problem. Hence an important issue is finding a good sampling or sketching scheme. Currently RandNLA algorithms use one of two approaches in order to achieve relative-error approximations: they either construct suitable importance sampling probabilities or use random projections followed by uniform sampling.

A key concept in the analysis of RandNLA algorithms are the statistical leverage scores. For an n x d matrix A (n >= d), the leverage scores a defined as follows: Let U be an n x d orthogonal basis for the column space of A and let U_i be the i-th row of U. Then the statistical leverage scores are || U_i ||^2  ( ||  || denotes the l_2 norm). The concept of statistical leverage scores comes from regression analysis where they are used to detect outliers.

For least-squares approximation, traditional algorithms (Cholesky, QR or SV decomposition) take O(nd^2) time. A basic randomized algorithm first samples O(d log (d) / eps^2) rows of the input matrix A and the input vector b, using the leverage scores of A as importance sampling probabilities. It then solves the smaller least-squares problem to get an approximate solution x'.  The length of the resulting residual vector is a (1 + eps) approximation of the optimal residual || A x_opt - b ||. There are also bounds on the difference between x' and x_opt.

While it takes O(nd^2) time to calculate the leverage scores exactly, an approximation of the leverage scores can be computed faster. One alternative approach uses a fast JL-transform on A, after which the leverage scores are approximately uniform and hence importance sampling on the transformed matrix corresponds to sampling rows of the transformed matrix uniformly. The resulting algorithms run in roughly O(n d log(d / eps) + d^3 log^2 n / eps) time.

Similar ideas are also used for low-rank approximation. In addition to theoretical results, some RandNLA algorithms have already been implemented and evaluated in different scenarios with an emphasis on massive data sets (e.g human genomics and astronomy). There has also been work on implementing RandNLA algorithms in distributed environments.

After the tutorial, several speakers gave 30 minute talks on various topics related to RandNLA. Nick Harvey gave a survey on generalization of Chernoff bounds to matrices: given a set of random, square, symmetric matrices, we want to show that their sum is close to the expected value of the sum. Here, closeness is expressed by bounds on the smallest and largest eigenvalues. Nick introduced Rudelson's Sampling Lemma, the Ahlswede-Winter inequality and Tropp's user-friendly tail bounds, which work in increasingly general settings.

Next, Nikhil Srivastava talked about graph sparsification with a focus on spectral sparsification. A graph H on the same vertices as graph G is a spectral sparsifier for G if the Laplacian of H gives a good approximation of the Laplacian quadratic form of G. Spectral sparsifiers can be constructed with a sampling scheme that uses effective resistances. For a Laplacian L = B^T W B (B is the incidence matrix and W contains the edge weights), these effective resistances are the leverage scores of W^1/2 B. In the case of effective resistances, the sampling probabilities can be computed quickly using Laplacian solvers.

The following two talks discussed practical implementations of RandNLA algorithms. Haim Avron described joint work with Petar Maymounkov and Sivan Toledo. When NLA algorithms are used as subroutines of larger applications, deterministic error bounds and a poly-log dependence on the accuracy are desirable. This can be achieved by using the randomization ideas described above to construct a preconditioner for an iterative algorithm (e.g. CG, LSQR, etc.). The right sampling strategy then leads to a well-behaved matrix and the problem can be solved with a small number of iterations. Empirical results show that a corresponding implementation can be faster than LAPACK (the state of the art) on dense matrices.

Ilse Ipsen spoke about aspects of the practical implementation outlined above (joint work with Thomas Wentworth). Given a matrix Q with orthonormal columns, we want to sample rows from Q so that the resulting matrix has a good condition number. They compare different row sampling schemes and give bounds for the condition number of the resulting matrix based on the coherence of Q. They also conducted numerical experiments and give tighter bounds on the condition number based on the leverage scores of Q.

Yiannis Koutis made another connection to Laplacian linear systems and presented joint work with Gary Miller, Richard Peng and Alex Levin. The theoretically best solver relies on spectral sparsifiers as preconditioners for solving Laplacian / SDD (symmetric diagonally dominant) systems. In contrast to the full sparsifiers described by Nikhil, the algorithm relies on incremental sparsifiers, i.e. a sequence of preconditioners, which are constructed with low-stretch spanning trees. While this algorithm has not been implemented yet, similar ideas have been used in CMG, which is a solver combining the multigrid method with cut-based graph sparsification.

Anastasios Zouzias talked about solving Laplacian systems in the Gossip model (joint work with Nikolaos Freris). The Gossip model is a distributed model of computation where each node can only communicate with its direct neighbors. Moreover, the input is split so that each node has only a single coordinate of the input vector. At the end of the computation, each node has a single output coordinate. Their solution is based on the (randomized) Kaczmarz method, an iterative algorithm for solving linear systems that uses a single row of the Laplacian matrix in each iteration.

Next, Christos Boutsidis spoke about column-based matrix reconstruction (joint work with Petros Drineas and Malik Magdon-Ismail). The overall problem is to approximate a given matrix A with another matrix X that has rank at most k. Christos focused on the problem where we want to approximate A with either r columns of A or r linear combinations of columns of A. One motivation for this restriction is that approximations with actual data columns can be easier to interpret. Since good theoretical results for the r = k case are already known, the talk focused on the r > k case. The authors give deterministic algorithms for approximation in both the Frobenius and the spectral norm and match the lower bound in the spectral norm case.

David Woodruff returned to least-squares regression and discussed his recent results on algorithms running in input sparsity time (joint work with Ken Clarkson). While previous work relied on the fast JL transform for subspace embeddings, their algorithm is based on embeddings that make use of the subspace structure. In particular, it is sufficient to preserve the coordinates with large leverage scores. The subspace embedding is the same as the CountSketch matrix in data streaming. The resulting algorithm runs in time roughly O(nnz(A) + d^3 / eps^2), where nnz(A) is the number of nonzero elements in the matrix A (using iterative methods, this can be improved to a logarithmic dependence on 1 / eps). Similar techniques also work for low-rank approximation.

In the final talk of the workshop, Ben Recht gave a survey of matrix completion. In the matrix completion problem, we are given a low-rank matrix M with missing entries and have to fill the missing data. This problem is also known as the Netflix problem. Since minimizing the rank is NP-hard, we instead use the convex relaxation of the rank function, which is the nuclear norm (the sum of the singular values). This convex relaxation approach is similar to l_1-minimization in compressive sensing. For an m x n matrix A (m <= n) with rank r and coherence bounded by mu, the nuclear norm heuristic recovers A with high probability if we have at least C mu^2 n r log^6 n entries (C is a constant). The dependence on the coherence is necessary because each entry has to provide a similar amount of information about A.

More from Simons Institute

Alistair Sinclair asked me to post the following.

For #2; note that those with existing postdoc positions are eligible (the Simons people hope they'll be able to arrange a one-semester leave); positions are valid up to 6 years from PhD, so junior faculty are also OK.

The newly created Simons Institute for the Theory of Computing at UC Berkeley has recently posted the following announcements:

1. Details of programs for academic year 2013-14: http://simons.berkeley.edu

2. Research Fellow positions (application deadline Jan 15, 2013): http://simons.berkeley.edu/fellows.html [Opportunities for outstanding junior scientists to spend one or two semesters at the Institute in academic year 2013-14, in connection with one of its programs.]

3. Call for program proposals (deadline Dec 15, 2012): http://simons.berkeley.edu/submit_proposal.html [An invitation for groups of researchers to submit proposals for programs in the broad area of theory of computing and its relationship to other fields - typically one semester in length - to run at the Institute during Fall 2014, Spring 2015 or Fall 2015.] Please follow the links above for details.

Posts from FOCS (Part 3)

Continuing posts from FOCS, with several guest-writers and guest-editor Justin Thaler.


[Editor: This is Part 3 in our series of posts covering FOCS 2012. Part 4 will be coming in the next couple of days, and there might or might not be a Part 5. We start with Harvard post-doc Karthekeyan (Karthik) Chandrasekaran , who contributes a summary of Nisheeth Vishnoi's talk on A Permanent Approach to the Traveling Salesman Problem from Session 2A on Sunday, October 21.]

Title: A Permanent Approach to the Traveling Salesman Problem.
Author: Nisheeth Vishnoi

Nisheeth gives a randomized algorithm to find a TSP tour of length at most n(1+O(1/sqrt(logk)) for simple k-regular graphs on n vertices. Both the algorithm as well as the analysis are simple and easy to state. The algorithm: pick a cycle cover, contract all cycles, find a minimum spanning tree in the resulting graph and output the tour consisting of the cycles and two copies of the edges in the tree. The cycles contribute to n edges and what we lose over n is bounded by the number of cycles. So, the goal is to pick a good cycle cover, one in which the number of cycles is small.

To pick a cycle cover, map the given graph to a bipartite graph by making two copies u_L and u_R for each vertex u, and adding edges (u_L, v_R) and (v_L, u_R) for each edge (u,v). Then find a perfect matching in the bipartite graph. Such a perfect matching can be mapped to a cycle cover in the original graph (such cycle covers could contain vertex-disjoint edges). Nisheeth shows that in the case of k-regular graphs, picking a uniformly random perfect matching in the bipartite graph leads to a good cycle cover with good probability. This is because:

- The number of perfect matchings in k-regular bipartite graphs (approx. equal to the number of cycle covers in k-regular graphs) is
the permanent of the adjacency matrix which is known to be large (per(A)=Omega(k^n) due to Egorychev, Falikman)

and

- The number of bad cycle covers (with large number of small cycles) in k-regular graphs is much smaller (by a counting argument).
Setting the parameters appropriately, this leads to at most n/sqrt(k) cycles with good probability.

To obtain a poly-time randomized algorithm, obtain a near-uniform perfect matching in the bipartite graph using Jerrum-Sinclair-Vigoda -- this increases the probability of picking a bad cycle cover only by 1/poly(n).

[Editor: Fourth-year grad student Michael Forbes of MIT contributes a summary of Mark Zhandry's talk on constructing quantum random functions from  Session 13A on October 23. Michael does a great job making this summary accessible even to non-quantum folks.]

Title: How to Construct Quantum Random Functions
Author: Mark Zhandry

Zhandry considers cryptography in the post-quantum world, where we want to have good cryptographic primitives despite the potential for quantum adversaries. There are two sides to this question.  The first part is determining which concrete problems seem hard for quantum computers to solve, and using them to construct concrete instantiations of cryptographic primitives.  As an example, it is well known that some concrete cryptographic schemes based on the hardness of factoring are broken because of Shor's algorithm, which can factor integers efficiently on a quantum computer. As such, post-quantum research in concrete cryptography has focused on primitives based on latticed-based problems.

Another side to this question, and this is what Zhandry considers, is identifying the relative structure of cryptographic primitives, such as determining which primitives can be constructed given other primitives.  As an example, it is classically known that one-way functions imply the existence of pseudo-random generators (PRG), which in turn imply the existence of pseudo-random functions (PRF). Zhandy answers the question (amongst others): does the implication "PRG=>PRF" still hold, assuming quantum adversaries?

We should note that there are two variants of the above question.  One variant allows the adversary to use a quantum computer, but only to interact with the cryptographic primitive in a classical way.  The more interesting variant that Zhandry considers is where the interaction can be quantum, and because of the nature of the quantum model,any query by the adversary can "involve" all of the PRF.  In the query model, quantum algorithms can be [provably] exponentially better than classical algorithms, so the adversary Zhandry considers is indeed powerful.

The "PRG=>PRF" result is commonly known as the GGM construction, based on the authors Goldreich-Goldwasser-Micali. They show how to take a PRG, stretching n bits to 2n bits, and from that produce a (seeded) family of functions from n bits to n bits, such that this family of functions is indistinguishable from random by a classical adversary.  The construction of this family is based on a large tree iterating the PRG on itself, where we split the PRG into the left n-bits and right n-bits, and plug one of these n-bits back into the PRG.  The input to the function family dictates the left/right pattern in which we apply the PRG. The security of this construction follows the standard hybrid argument approach.

The main difficulty in applying the above construction in the face of quantum adversaries, is that the hybrid argument in the classical case exploits that classical algorithms can only "look at" as many parts of the PRF as the runtime of the algorithm.  However, as mentioned above, quantum computers can "look at" the entire PRF even in a single query.  Thus, if one wanted to perform a hybrid argument, one might need exponentially many hybrids, which would result (by the averaging used in the hybrid argument) in an exponential (and thus unacceptable) loss in the parameters.

To get around this, Zhandry replaces the distribution of interest with another distribution (quantumly indistinguishable to small-query algorithms) such that this new distribution is created by intrinsically few parameters, so that any hybrid argument on this new distribution only needs to be over few hybrids, allowing the rest of the GGM argument to go through.  Specifically, consider a distribution D, and any r. If we choose a function g via D^[r] (that is, r random samples from D, indexed 1 through r) and f from [r]^X (that is, a random map from the space X to the numbers 1 through r), then g composed with f is a function giving each element in X a sample from D, while only involving r true samples from D.  When r goes to infinity, this distribution will converge to each element in X getting a uniformly random sample from D.  Further, Zhandry shows that for a fixed r, a quantum algorithm with q queries cannot distinguish this process from truly random samples with better than poly(q)/r statistical distance.  Thus, as the above random process only depends on r truly random samples, the hybrid argument will only involve r terms, and, once the choice of r is made, this allows the GGM analysis to be completed in this quantum setting.

NYCE (New York Computer Science and Economics Day) Announcement

I was asked to post the following:

We are pleased to announce that NYCE 2012, the fifth annual New York
Computer Science and Economics Day, will be held in New York City on
Monday, December 3rd.

** General Information
The goal of NYCE is to bring together researchers from the larger New
York metropolitan area interested in computer science, economics,
marketing, and business. This year, our organizing theme is ``The
Economics of Big Data, Information, and Privacy.''

NYCE features both invited talks and shorter contributed talks and
posters (see below for details). This year, our invited speakers are
Alessandro Acquisti (CMU), Moshe Babaioff (Microsoft Research), Tim
Roughgarden (Stanford), Michael Schwarz (Google), and Catherine Tucker
(MIT).

NYCE 2012 will be held at the Simons Foundation on December 3rd, from
9:00 a.m. to 5:00 p.m.

For more information, please go to our website:
https://sites.google.com/site/nyce1212/

** Contributed Talks and Posters
Students are invited to present their work in the form of posters or
short (10 minute) talks on any subject of interest to the NYCE
community; these include (but are not limited to) theoretical,
modeling, algorithmic, and empirical work on advertising and marketing
based on search, user-generated content, social networks, or other
means of monetizing the Internet. If you are interested in presenting
your work at NYCE, simply submit an abstract by Thursday, November 8th
(3 days after the STOC deadline).

** Registration
Advance registration (free, thanks to our generous sponsors) is now
open. You can register at
https://sites.google.com/site/nyce1212/registration/ until November
20th. After that date, on-site registration is available for a fee of
$25.

-- Dirk Bergemann, Sham Kakade, Nitish Korula, and Aaron Roth.

Posts from FOCS (Part 2)

Continuing posts from FOCS, with several guest-writers and guest-editor Justin Thaler.

[Editor: First-year grad student Mark Bun of Harvard contributes a summary of two talks on submodular maximization from Session 13A on Tuesday, Oct. 23]

We had not just one, but two talks on new tight algorithms for submodular maximization. A submodular function is a set function whose value offers diminishing returns to its input. That is, adding some element to a set causes a smaller increase in the value of the function than does adding that element to a subset. Many combinatorial optimization problems can be expressed as the minimization or maximization of a submodular function, including min- and max-cut, coverage problems, and welfare maximization in algorithmic game theory. Unsurprisingly, submodular maximization tends to be NP-hard for most natural choices of constraints, so we look for approximation algorithms. Both results regard the input submodular function as a value oracle, which evaluates the function on a set in one time step.

Paper Title: A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

Roy Schwartz spoke about work with Niv Buchbinder, Moran Feldman and Seffi Naor on a randomized linear-time 1/2-approximation for unconstrained submodular maximization. This matches a lower bound due to Feige, Mirrokni and Vondrak, who showed that achieving any approximation factor larger than 1/2 requires exponentially many queries to the value oracle. That paper also gave a 2/5-approximation based on local search, which was later improved to 0.41 by Gharan and Vondrak by simulated annealing, and then to 0.42 by Feldman, Naor and Schwartz by taking advantage of structural similarity. Given this line of work, the result here is remarkable for being both tight and incredibly simple. It is essentially a greedy algorithm that exploits both randomness and the symmetry of the optimization problem.

Paper Title: A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint.

Justin Ward then presented a new tight algorithm for monotone submodular maximization subject to a matroid constraint, in joint work with Yuval Filmus. Calinescu et al. gave a tight approximation where they relaxed the problem to continuous space, performed gradient ascent, and then rounded. This algorithm achieves the same approximation, but is purely combinatorial. It works by applying the standard greedy algorithm to an auxiliary potential function that has lower curvature than the input function. One of the neat parts of this talk was a discussion of how the authors came up with this auxiliary function. It was quite the tale of experimenting with matroids of low-rank, solving an LP, and guessing a necessary recurrence.

===================

[Editor: Fourth-year grad student Michael Forbes contributes a summary of Ketan D. Mulmuley's talk on Geometric Complexity Theory from Session 12B on Tuesday, October 23.]

Paper Title: Geometric Complexity Theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether's normalization lemma

Ketan starts with the following problem. Consider the space of t-tuples of n by n complex matrices. We impose an equivalence relation on this space via simultaneous conjugation by a fixed matrix. For example, when t=2, we consider (A,B) and (PAP^{-1},PBP^{-1}) equivalent, for any invertible matrix P. The question is to classify the equivalence classes under this action, by identifying a suitably nice normal form. In this context, "nice" means that t-tuples in normal form are the solutions-to/parameterized-by some polynomial equations.

For t=1, this problem is solved by the Jordan normal form. For t>1, this problem is considered "wild". That is, this problem is considered quite difficult in representation theory, and any other problem that embeds this classification problem is called "wild". This problem is similar to hard problems in complexity theory, as it can be shown that the t=2 case embeds the t>2 case, so there is some sort of "completeness" result going on.

It is classically known that Noether's normalization lemma is at the heart of the above classification problem. This lemma states that there exist some set S of generators, such that a certain ring is integral over the ring generated by S. Further, a random choice of S will work. In his paper, Ketan argues that explicit derandomization of the polynomial identity testing (PIT) problem will imply explicit sets S of generators as needed for Noether's lemma, which would imply explicit classification of the "wild" problems mentioned above. That is, the (black-box) PIT problem is to construct a small set H of evaluation points, such that for any small algebraic circuit C computing a non-zero polynomial, C will evaluate to non-zero on some point in H.

The PIT problem has seen a lot of interesting work in the past decade, much of it focused on constructing such sets H (called hitting sets) for restricted classes of circuits, such as depth-3 circuits with bounded fan-in. Ketan suggests that because the general PIT question embeds these wild problems from representation theory, there is a tension between the consensus in the two fields: representation theory sees these classification problems as notoriously difficult, while complexity theory might suggest that these problems (via their connection to PIT) are possible to solve (but perhaps still difficult).

=====================

[Editor: Third-year grad student Thomas Steinke of Harvard contributes a summary of two talks on pseudorandomness from Session 2B on Sunday, October 21.]

FOCS 2012 had very many interesting talks. I'll discuss two papers on

unconditional pseudorandom generators, namely Pseudorandomness from Shrinkage by Russell Impagliazzo, Raghu Meka, and David Zuckerman (speaker) and Better Pseudorandom Generators from Milder Pseudorandom Restrictions by Parikshit Gopalan, Raghu Meka (speaker), Omer Reingold, Luca Trevisan, and Salil Vadhan.

Both of these papers show a connection between pseudorandom generators and (pseudo)random restrictions.

Random restrictions are often used to prove lower bounds for circuits, branching programs, or other models of computation. Typically one shows that a circuit `simplifies' or `shrinks' when a random subset of its inputs are set to random values. For example, Hastad's switching lemma is used to show that an AC0 circuit reduces in depth each time a random restriction is applied. However, the parity function does not simplify when restricted. Thus proving that parity is not in AC0.

A pseudorandom generator for a function family immediately gives a lower bound for such functions. Meka et al. give a partial converse to this by converting a lower bound analysis using random restrictions into a pseudorandom generator. They show that, if a pseudorandom restriction sufficiently shrinks circuits in a given family, then a pseudorandom generator can be constructed that essentially matches the lower bound given by the analysis. Thus this paper adds to the well-known connection between hardness and randomness. Their work yields pseudorandom generators with polynomial stretch for several models, including near-quadratic stretch for branching programs that can read their input in an arbitrary fixed order, while the previous best result gives linear stretch.

Gopalan et al. also analyse pseudorandom restrictions, but with very different techniques and results. They analyse mild restrictions (i.e. only a constant fraction of input bits are restricted) that do not yield the strong shrinkage required by Meka et al.. They are able to show that these restrictions, when `averaged out,' leave a function that is fooled by a small bias distribution. Recursively applying this analysis yields a pseudorandom generator with near-optimal almost-logarithmic seed length for combinatorial rectangles and read-once CNFs, as well as a hitting set generator for width-3 branching programs. Previous work was only able to achieve these results with large error; when the error of the pseudorandom generator is required to be polynomially small, their results are a polynomial improvement in terms of seed length.

=====================

[Editor: Fourth-year grad student Justin Thaler of Harvard contributes a summary of two unrelated talks.]

Paper Title: The Cutting Plane Method is Polynomial for Perfect Matchings.

Harvard's own Karthekeyan Chandrasekaran talked about joint work with Laszlo A. Vegh and Santosh S. Vempala on cutting plane algorithms for matching problems. The cutting plane method is a popular algorithm for solving integer programs (IPs), used in commercial solvers. It works by starting with an LP relaxation of the given IP to obtain basic optimal solution x_0, and then iteratively adding constraints that are valid for integer solutions but violated by the basic optimum. It continues until the basic optimum is integral. The goal of this paper is to take a step toward explaining the practical efficiency of cutting plane methods, by giving an efficient cutting-plane algorithm for min-cost perfect matching (MWPM) --MWPM is known to be in P, but it was open (apparently for 30 years) whether there was a polynomial-time cutting-plane algorithm for this problem.

A brief summary of how they achieve this is as follows. They start with a natural, well-known LP relaxation of the MWPM problem, called the bipartite relaxation. This relaxation has the nice property that all basic optima x are half-integral, and the support of x is a disjoint union of edges and odd cycles. This makes it easy to find cuts (the cuts correspond to what are called blossom inequalities, see the paper for details). A major challenge, though, is that naively adding cuts will not preserve the half-integrality of intermediate LPs, so at each iteration they throw away some of the old cuts that were added earlier in the execution. They need to take considerable care in choosing which cuts to keep in order to guarantee half-integrality of intermediate LPs (and to ensure that their algorithm makes progress at a sufficiently high rate).

Paper Title: Lower bounds on information complexity via zero-communication protocols and applications.

I unfortunately didn't catch the name of the presenter, but this work was by Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jeremie Roland and David Xiao. As the title states, this paper was about information complexity. The idea underlying this concept is as follows. In the standard two-party communication model, Alice and Bob have inputs x and y respectively, and they communicate with each other in order to compute a function f(x, y), with the goal of minimizing the total number of bits transmitted; this is the communication cost CC. Even if Alice and Bob exchange a lot of bits, we can still ask how much information about Alice's input was revealed to Bob, and vice versa; this is the information cost IC. In principle, this could be much smaller than the total communication, as a message can sometimes reveal less information than its length.

As far as I can tell, people started studying IC precisely because it provided a way to reason about and lower bound CC (it is easy to see that the amount of information revealed about the inputs is never larger than the total communication), but IC is a natural complexity measure in its own right, and determining the precise relationship between IC and CC (i.e. whether it is possible to ``compress communication down to the information complexity'') is still a major open question. This is the context underlying the paper, and finally here is a summary of the results.

The authors given a new method, called the relaxed partition bound (RPB), for lower bounding the information complexity of any function. The proof that the RPB indeed lower bounds IC goes through a new connection between "zero-communication protocols" and information complexity-- see the paper for details. Remarkably, the RPB method is stronger than almost all known methods for lower bounding the *communication* complexity f (the only exception is the (unrelaxed) partition bounded itself). Essentially this means that any existing CC lower bound proved via a technique other than the partition bound is actually something stronger: it is an IC lower bound. They are therefore able to resolve the information complexity of a number of important problems, resolving three open questions from a STOC 2012 paper by Mark Braverman.