Posts from FOCS (Part 1)

Justin Thaler went to FOCS, and managed to arrange for various people to write up their thoughts on various parts of the conference.  So Justin is the famed Editor below.  We haven't seen much posted about FOCS, so hopefully these summaries will be of interest.  I expect we'll have a few posts in this series.

[Editor: Third-year grad student Matt Weinberg of MIT contributes a summary of many of the EconCS talks from FOCS. Matt starts with the Workshop on Bayesian Mechanism Design on Saturday, October 20, followed by some talks from the main program.]

Missing: Jason Hartline, Introduction to Bayesian Mechanism Design, and Tim Roughgarden, Simple/Prior Independent mechanisms part A.

1) Tim Roughgarden, Simple/Prior Independent mechanisms part B: For some settings, such as selling a single item, the revenue-optimal auction is well understood but difficult to implement in practice. On the other hand, the second price auction (item goes to the highest bidder, she pays the second highest price), is often used in practice but has absolutely no revenue guarantee. A famous theorem in Economics of Bulow and Klemperer helps explain this: While the second price auction itself has no revenue guarantee, the revenue of the second price auction after recruiting one extra bidder is at least as good as the optimal auction (without recruitment). In other words, a seller's efforts are better spent advertising than analyzing the market (in these scenarios).

In addition to presenting this theorem, Tim discussed several extensions of this theorem. In a paper with Jason Hartline, they showed that in more complex settings (called "single-dimensional"), the spirit of Bulow-Klemperer holds: simple auctions yield approximately optimal revenue. In a paper with Peerapong Dhangwatnotai and Qiqi Yan, they show further that one can obtain approximately optimal revenue via a simple auction with very limited information about the market. With Inbal Talgram-Cohen and Qiqi Yan, they showed that such results are also possible in certain multi-dimensional settings, such as matching markets.

2) Costis Daskalakis, Revenue Optimization in Multi-Item Auctions: As mentioned in Tim's talk, revenue-optimization in single-item auctions is very well understood. Not only does this mean that revenue can be optimized exactly with enough work, but it enables the study of simple, approximately optimal auctions such as those presented by Tim. Unfortunately, as soon as a second item enters the picture, all bets are off and all of a sudden we know absolutely nothing. Not only do we not know what the optimal auction looks like, but we don't have any grasp on a good benchmark for designing approximations in general settings (in certain restricted settings, Shuchi Chawla, Jason Hartline, David Malec and Balasubramanian Sivan were able to approximate a meaningful benchmark via a clever multi- to single-dimensional reduction). In contrast, welfare maximization is extremely well understood, and has been for 40 years, 10 years before we knew how to maximize revenue with even a single item.

Costis presented work with Yang Cai and Matt Weinberg showing that in very general multi-dimensional settings, revenue maximization can be computationally efficiently reduced to welfare maximization. Specifically, the mechanism design problem of maximizing revenue is reduced to the algorithm design problem of maximizing welfare (without worrying about incentives).

3) Nicole Immorlica, Black Box Reductions from Mechanism to Algorithm Design: One could argue that the overarching goal in mechanism design is to reduce problems with incentives (such as maximizing an objective subject to truthfulness constraints) to problems without (such as designing an algorithm to optimize some objective on all inputs). Several famous economic results, such as the second-price auction, VCG (to maximize welfare), and Myerson's (to maximize revenue selling a single item) follow this paradigm. In fact, so does the main result presented in Costis' previous talk. An obvious important question is simply "when can such reductions exist?" and more specifically, "when are they compatible with approximation algorithms?"

Nicole presented work by Jason Hartline and Brendan Lucier, which shows that in all Bayesian, single-dimensional settings an alpha-approximation algorithm for welfare implies a Bayesian truthful alpha-approximation mechanism for welfare. Follow-up work done independently by Jason Hartline, Robert Kleinberg, and Azarakhsh Malekian and Xiaohui Bei and Zhiyi Huang showed that the same result holds in multi-dimensional settings as well. In a more recent paper, Nicole with Shuchi Chawla and Brendan Lucier provided some negative results, essentially showing that these techniques will not apply far beyond these settings. They show first that it is not possible to replace Bayesian truthfulness with deterministic truthfulness, even in single-dimensional settings. They also show that it is not possible to replace welfare with a non-linear objective (such as makespan).

4) Shuchi Chawla, Non-Linear Objectives in Mechanism Design: Non-linear objectives, such as minimizing makespan, have proven much more difficult to handle in mechanism design than linear ones, such as welfare. Specifically, consider the problem where there are n jobs that need to be run on one of m machines. Each machine i reports a processing time t(i,j), and the goal is to allocate the jobs to machines in a way that minimizes the makespan (maximum processing time among the machines). In the single-dimensional version of this problem, Aaron Archer and Eva Tardos showed how to obtain a 3-approximation, and Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, and Tim Roughgarden later gave a PTAS. For the general problem, Noam Nisan and Amir Ronen showed that VCG only obtains an m-approximation and Itai Ashlagi, Shahar Dobzinski, and Ron Lavi later proved that no natural, truthful mechanism can do better (for a very reasonable definition of natural mechanisms).

Shuchi presented joint work with Jason Hartline, David Malec, and Balusabramanian Sivan that beats this hardness result using Bayesian truthfulness, obtaining a constant factor approximation whenever n = O(m). In some sense, this is the "hard" case of the problem. In light of the hardness result from Nicole's previous talk, the mechanism cannot simply be a black-box reduction to algorithm design, but instead uses novel ideas.

5) Eva Tardos, Price of Anarchy of Practical Auctions: The price of anarchy studies the effect of selfish behavior in games. In order to minimize congestion in a network, a central designer might try to enforce that certain users use certain paths. As this is quite a daunting task, one might instead hope that simply letting users choose their own paths will result in good (but perhaps not optimal) congestion. In a 2001 paper, Tim Roughgarden and Eva Tardos showed exactly this: that as long as users choose paths in a Nash Equilibrium, the congestion is only a constant-factor worse than optimal. Since then, several other games were shown to have a good price of anarchy, including several auction scenarios. 

Until recently, all of these results were proved using different techniques, and every new game required a new key insight to prove a PoA bound. In addition, once interest grew to other solution concepts beyond Nash Equilibrium, each setting had to be revisited and reproved. In 2009, Tim Roughgarden introduced a "smoothness" technique which essentially reduced proving PoA bounds for several solution concepts to proving that a game (or auction) was "smooth." Eva presented recent work with Vasilis Syrgkanis and Renato Paes Leme where they extend the smoothness framework to accommodate auctions and combinations of auctions. They show first that several practical auctions, including first price auctions and second price auctions (under some mild assumptions) are "smooth." Second, they show that any sequential or parallel combination of smooth auctions is itself smooth (also under some natural assumptions), and therefore has good price of anarchy in several solution concepts. This nicely models lots of practical settings (such as participating in multiple auctions over ebay) and shows that simplicity doesn't cost us much.

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

[Editor: Matt also contributes a summary of the AGT Session (3A) from Sunday October 21st].

Session 3A:

1) Yang Cai, Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization (joint work with Costis Daskalakis and Matt Weinberg): Designing a revenue-maximizing auction for multiple items is one of the central open problems in mathematical economics (see summary of Costis' workshop talk for more background on the problem). An ideal solution, especially for computer scientists, would be one that reduces the problem of designing the auction (a problem that must respect bidder's incentives) to the problem of designing an algorithm (a problem with no incentive constraints). This paper does exactly that in very general settings.

The main idea is that the revenue-maximizing auction can be described as a solution to an LP with polynomially many variables but exponentially many constraints. Remarkably, a separation oracle for the feasible region can be constructed using only black-box access to an algorithm that maximizes welfare (without concern for incentives). See Tim Roughgarden's summary of this talk by Costis here: http://agtb.wordpress.com/2012/08/29/cmu-summer-school-recap-part-3-hartline-and-daskalakis/.

2) Zhiyi Huang, The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal (joint work with Sampath Kannan): Traditional mechanism design usually focuses on maximizing (or nearly maximizing) an objective subject to truthfulness constraints. Traditional differential privacy focuses on maximizing an objective subject to privacy constraints. This paper explores the possibility of obtaining all three goals simultaneously. In this paper, the authors show that the Exponential mechanism, a well-studied mechanism from differential privacy, is actually truthful as well. In other words, truthfulness is compatible with differential privacy,at least for maximizing welfare.

The main idea is that the Exponential mechanism is a maximal-in-distributional-range mechanism, offset by the Shannon entropy. MIDR mechanisms are known to be truthful. They also show that in several settings, the mechanism can be implemented efficiently.

3) Laszlo Vegh, Concave Generalized Flows with Applications to Market Equilibria: Concave generalized flow networks build upon standard flow networks. In a traditional flow network, when x flow leaves node v on a path to w, x flow arrives at w. In a Concave generalized flow network, every edge has a concave, monotone gain function, so that when x flow leaves node v on a path to w, g_e(x) flow arrives at w instead. The goal is still to maximize the flow arriving at the sink. This problem (and the special case where every gain function is linear) has been extensively studied, and can be solved via convex programming. However, until this result, no combinatorial algorithm was known (that applied in all settings).

The paper provides a combinatorial algorithm with quite good running time (not much worse than just solving a regular network flow), and also provides new applications to finding market equilibria. Specifically, the paper shows that equilibrium for Linear Fisher markets (and also other market equilibrium solutions) can be found using concave generalized flows.

STOC deadline extended

Due to inclement weather, the deadline for STOC submissions has been extended to Monday, November 5, at 5:00 pm EST.   Check the STOC web page for more details

WSDM 2013 Accepted Papers

The list of papers accepted to WSDM 2013 is now up.  Looks like the usual fun mix of papers.

Crimson Series on the Ad Board

The Harvard Crimson just finished a four-part series looking at the Harvard Ad Board since the reforms a couple of years ago.  I must admit I didn't find the articles very insightful, but they offered a glimpse as to some of the changes and current feelings about the Ad Board.  The first part begins here, and from there you can find links to the rest of the articles.

STOC 2013 Submissions

I was asked to post the following regarding STOC 2013 submissions:

1) Please read the Call for Papers carefully and pay special attention
to length and formatting requirements, which have changed since last
year:
    a) Submissions must be no more than 10 pages in two-column ACM
Proceedings format, including the bibliography.
    b) Length and formatting requirements will be enforced strictly
and literally; submissions that don't conform will be summarily
rejected.
Note that you have the option of uploading a full-paper version, along
with your 10-page extended abstract.

2) The online submission process will take more time than it has in
the past for at least two reasons:
    a) There are roughly three times as many Program-Committee members
as in the past, and thus Conflicts of Interest will take longer to
check off.
    b) Each author is required to select one or more Topics (from a
moderately long list) that describe his or her submission.
Thus we strongly suggest that you create your user account on the
submission server NOW and fill in a "start new paper" form for each
submission, even if you have not yet finished writing it.  Submissions
can be modified any time between now and the deadline of Nov. 2, 2012
at 04:59 pm EDT.

Note that this and all other information about STOC 2013 can be found
at http://theory.stanford.edu/stoc2013/

Giving a Teleseminar

The nice folks at Texas A&M asked me to give a teleseminar as part of their series.  So instead of flying all the way to Texas to give a talk, I did so from the comfort of my office, using Cisco's WebEx.  It was, I believe, the first formal teleseminar I've given.  I imagine that it's the future of talks, so I thought I'd share my thoughts on the experience.

Overall, technically, it went just fine.  Any slight hiccups were managed easily.  I was working in my office and not paying attention to the clock, so they had to e-mail me and remind me to get online for the talk.  (Oops.)  When I logged in at first the sound didn't work for some reason, but logging in again all was fine, and we started pretty much on time.  They could see the slides on my laptop, they had a camera image of me and I had an image of them, and after the initial bump the sound seemed to work the entire time (at least on my end, and I think I spoke loudly enough it was not a problem on their end).  At this point the technology is really there to do this sort of thing, so if anything I'm surprised there's not more of this type of seminar being done.

Pros:  Obviously, from my standpoint, not flying to give a talk.  I'm going to Cornell to give a talk in a couple of weeks, and while I'll undoubtedly enjoy the face time with the many great people at Cornell I'll get to see, I won't enjoy the multiple nights away from my family, or the multiple hours flying to get there.  (One could arrange the Web equivalent of face to face time with teleseminars quite easily -- set up Skype sessions or a Google hangout for the day.)

Another pro is that people online could log in, watch the talk, and ask questions as well.  That can also be done with standard talks, although it seemed to me the real-time asking of questions is a bit more awkward when the speaker is there live with the audience rather than online.

Cons:  You don't get that face to face time with the people at the home institution that can, sometimes, work out so well.  I've had someone giving a talk at Harvard come to my office for the standard chat-with-the-visitor session and had the solid beginning of a paper by the time they left.  I don't know if serendipity works the same online yet.

The biggest downside was the setup made it hard for me to gauge the audience reaction, which would have been really helpful for this talk.  I was talking about hashing data structures like Bloom filters to a primarily EE audience, so for all I knew I could have been going way over their head, boring them silly, or been pretty much on target.  I wasn't able to see how they were responding and adjust accordingly.  I think I needed a second (very big) screen in front of me -- one devoted to my slides, and one large, full screen instead of a little window big enough so I could watch the audience react, the way I do in a live lecture.  This might have been easy enough to set up had I knew how useful it would be ahead of time.  I tried to ask during the talk and it seemed like I was targeting the right level, but that type of on-the-fly correction would have been easier to make if I were actually there.    

Conclusion:  I would happily give a teleseminar like this again.  Until my kids are older and I feel like traveling more instead of less, this may become my preferred method of giving talks (except, possibly, for California;  I'm generally always happy to have an excuse to go to California, but even then, timing might make a teleseminar preferable sometimes).  I'm surprised there aren't more schools or organizations adopting and experimenting with this approach.  It seems both cost-effective and time-effective.    Thanks to Texas A&M for inviting me to try it.

Harvard Center for Research on Computation and Society (CRCS) Postoc / Visiting Scholar Call

Harvard's CRCS is looking for postdocs!  Please apply....

We're very interested in theorists (and, of course, non-theorists as well!) in all of the areas listed below.  Also, for those who know of my work with Giorgos Zervas -- well, he's finishing his postdoc this year, and I'd be thrilled to find other people to work with on the semi-theoretical semi-data-focused EconCS style work.  

Spread the word...

----------

The Harvard Center for Research on Computation and Society (CRCS) solicits applications for its Postdoctoral Fellows and Visiting Scholars Programs for the 2013-2014 academic year. Postdoctoral Fellows are given an annual salary of approximately $60,000 for one year (with the possibility of renewal) to engage in a program of original research, and are provided with additional funds for travel and research support. Visiting Scholars often come with their own support, but CRCS can occasionally offer supplemental funding.

We seek researchers who wish to interact with both computer scientists and colleagues from other disciplines, and have a demonstrated interest in connecting their research agenda with societal issues.  We are particularly interested in candidates with interests in Economics and Computer Science, Health Care Informatics, Privacy & Security, and/or Technology & Accessibility, and those who may be interested in engaging in one of our ongoing/upcoming projects:

- Intelligent, Adaptive Systems for Health Care Informatics
- Language-Based Security
- Personalized Accessibility
- Privacy and Security in Targeted Advertising
- Privacy Tools for Sharing Research Data
- Trustworthy Crowdsourcing

Harvard University is an Affirmative Action/Equal Opportunity Employer. We are particularly interested in attracting women and underrepresented groups to participate in CRCS.

For further information about the Center and its activities, see http://crcs.seas.harvard.edu/.


Application Procedure

A cover letter, CV, research statement, copies of up to three research papers, and up to three letters of reference should be sent to:

Postdoctoral Fellows and Visiting Scholars Programs
Center for Research on Computation and Society
crcs-apply@seas.harvard.edu

References for postdoctoral fellows should send their letters directly, and Visiting Scholar applicants may provide a list of references rather than having letters sent. The application deadline for full consideration is December 16, 2012.

Allerton Panel

This year was the 50th Annual Allerton Conference on Communication, Control, and Computing (website).  Hard to believe it's been around that long.  I think my first year there was 1999, and while I haven't gone every year, I've been to Allerton regularly since.  

I happily got to be the token (theoretical) computer scientist on one of the panels, where one of the questions was specifically whether the interaction between communications/control and theoretical computer science had been healthy. I found it interesting that two co-panelists Alexander Vardy and Muriel Medard both had opinions very similar to mine.  If you looked about 10-15 years ago, you might have been very optimistic about what I'll call the "theoretical electrical engineering" community and the "theoretical computer science" community coming together in a big way.  There had been some significant successes -- specifically, in the Guruswami-Sudan work on list decoding, and work on low-density parity-check coding (including the paper by Luby-Mitzenmacher-Shokrollahi-Spielman).  Codes were clearly becoming important on the complexity side in TCS, and algorithmic considerations were becoming more important in TEE.  

And while there's been the occasional crossover subject since then -- people on both sides of the aisle work on network coding, though it still seems more clearly a TEE subject than a TCS subject, and compressed sensing and even social networks have taken hold in both TEE and TCS -- there's still surprisingly little interaction between the two communities, especially since, more and more, I think the two communities are growing ever closer intellectually.  (I tried to spin some fun thoughts on that during the panel -- TEE sprung from Shannon, focusing on communication and transmission rate;  TCS sprung from Turing, focusing on computation and computational complexity.  And for fifty years or so, the two subjects have carved out fairly distinct sets of problems.  But as the distinction between "communication" and "computation" continues to fall away, the sets of problems the two groups work on get ever closer together.) 

Culturally, however, TEE and TCS seem quite different, not just with different conferences and journals, but different ideas about measuring research and publications.  (Conferences don't really count for TEE, while journals don't really count for TCS.)  Perhaps this inertia keeps the two communities apart.  Or perhaps there's something else that I'm missing, but several younger people after the panel came up to me afterwards and seemed to agree.  They wanted to be able to move back and forth between the communities, as the problems they were interested in seemed relevant to both (and possibly or probably needed techniques from both to fully tackle the problems), but the divide between them seemed rather large, and the best way forward career-wise seemed to be to stick with one or the other.  

So the panelists seemed to agree with their sense of mild disappointment that the past decade hadn't really lived up to its potential in terms of TCS and TEE combining forces to meet their intellectual challenges, but still remaining optimistic that there were opportunities there.  

I'm told the recording of the panel will go on line at some point;  I'll link to it when it is.  

Harvard CS Is Hiring

Tenure Track Position Open.  Here's the official blurb:

Tenure-track Position in Computer Science

The Harvard School of Engineering and Applied Sciences (SEAS) seeks applicants for a position at the level of tenure-track assistant professor in Computer Science, with an expected start date of July 1, 2013.

Candidates are required to have a PhD or an equivalent degree by the expected start date.  In addition, we seek candidates who have an outstanding research record and a strong commitment to undergraduate teaching and graduate training.

This is a broad search, and we welcome outstanding applicants in all areas of computer science.  This includes applicants whose research and interests connect to such areas as computational science, engineering, health and medicine, or the social sciences.

Required application documents include a cover letter, CV, a statement of research interests, a teaching statement, up to three representative papers, and names and contact information for at least three references.  Applicants will apply online athttp://academicpositions.harvard.edu/postings/4324.

The Computer Science program at Harvard University benefits from outstanding undergraduate and graduate students, an excellent location, significant industrial collaboration, and substantial support from the School of Engineering and Applied Sciences.  Information about Harvard's current faculty, research, and educational programs is available athttp://www.seas.harvard.edu.

We encourage candidates to apply by December 1, 2012, but will continue to review applications until the position is filled.  Harvard is an Equal Opportunity/Affirmative Action Employer.  Applications from women and minority candidates are strongly encouraged.

Student Bragging....

Always worth bragging about my students...

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

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

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

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

By the Numbers

Pretty much matching my predictions....

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

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

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

Back to work now -- class to prep!

Happiness Is...

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

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

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

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

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

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


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

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

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

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

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

Uncertainty

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Honor Codes?

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

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

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

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

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

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

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

Max Flows in O(nm) Time by Orlin

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

Academic Dishonesty Cases

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

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

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

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

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

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

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

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

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

Important IP Case

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

In particular, the latest things that really interested me:

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

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

Mail Issue

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

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

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

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

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

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

 

Distracting Videos

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

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

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

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

Article about DEC Folk

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

Like a Movie Meteor...

The new semester is hurtling toward me.

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

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

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

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

Yale Daily News, continued

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

MMDS

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

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

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

Fun stuff!

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

On NPR (Morning Edition)

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

Anniversary

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

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

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

    

Simons Institute Call

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

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

New SIGACT Officers

Lance informs me we have newly elected officers at SIGACT.

Chair:  Paul Beame

Members-at-Large:

Venkatesan Guruswami
Rocco Servedio
Avrim Blum
Tal Rabin

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

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

Mihai Memorial Blog

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

Dear friends of Mihai,

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

Best regards,
Mikkel and Alex

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

Sad Passing: Mihai Patrascu

[** UPDATE **]

Dear friends of Mihai,

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

Best regards,
Mikkel and Alex

[** UPDATE END **]



Mikkel Thorup just sent me the following to post regarding Mihai Patrascu. 

---------------

Mihai Patrascu, aged 29, passed away on Tuesday June 5, 2012, after a
1.5 year battle with brain cancer. Mihai's carreer was short but
explosive, full of rich and beautiful ideas as witnessed, e.g., in his 19
STOC/FOCS papers.

Mihai was very happy about being co-winner of the 2012 EATCS Presburger Young Scientist Award for his ground-breaking work on data
structure lower-bounds. It was wonderful that the community stood up
to applaud this achievement at STOC'12. Unfortunately he will not make it to the award ceremony on July 10 at ICALP.  Mihai's appreciation
for the award shows in the last post on his blog
http://infoweekly.blogspot.com/.

I was fortunate enough to be one of Mihai's main collaborators. One of
the things that made it possible to work on hard problems was having
lots of fun: playing squash, going on long hikes, and having beers
celebrating every potentially useful idea.

On this last note, Mihai's wife Mira tells me that she does not want
any flowers and that his funeral will be back in Romania.
However, she wants people to have a glass of wine in Mihai's memory,
thinking about him as the inspired and fun young man that he was.

Verification in the Cloud [Guest Post by Justin Thaler]

[Justin talks about his upcoming work, to be presented at HotCloud.]

For the past few years, Michael and I, along with our awesome collaborators, have worked towards developing practical protocols for verifying outsourced computations. In roughly chronological order, the relevant papers are here , here , here , here , and most recently here . In this last paper (joint work with Mike Roberts and Hanspeter Pfister ), we really tried to push these protocols into practice, largely by taking advantage of their inherent parallelizability: we'll be presenting it at HotCloud next week, and it is the main impetus for this blog post. My hope here is to give a (somewhat) brief, unified overview of what we've accomplished with this line of work, and how it relates to some exciting parallel lines of inquiry by other researchers.

Our main motivation is that of Alice, who stores a large data set on the cloud, and asks the cloud to perform a computation on the data (say, to compute the shortest path between two nodes in a large graph, or to solve a linear program defined over the data). Of course, Alice may be a company or an organization, rather than an individual. The goal is to provide Alice with a guarantee that the server performed the requested computation correctly, without requiring Alice to perform the requested computations herself, or even to maintain a local copy of the data (since Alice may have resorted to the cloud in the first place because she has more data than she can store). In short, we want to save Alice as much time and space as possible, while also minimizing the amount of extra bookkeeping that the cloud has to do to prove the integrity of the computation.

Alice may want such integrity guarantees because she is concerned about simple errors, like dropped data, hardware faults, or a buggy algorithm, or she may be more paranoid and fear that the cloud is deliberately deceptive or has been externally compromised. So ideally we'd like our protocols to be secure against arbitrarily malicious clouds, but sufficiently lightweight for use in more benign settings. This is an ambitious goal, but achieving it could go a long way toward mitigating trust issues that hinder the adoption of cloud computing solutions.

Surprisingly powerful protocols for verifiable computation were famously discovered within the theory community several decades ago, in the form of  interactive proofs , PCPs , and the like. These results are some of the brightest gems of complexity theory, but as of a few years ago they were mainly theoretical curiosities, far too inefficient for actual deployment (with the notable exception of certain zero-knowledge proofs).

We've been focusing on interactive proof methods, and have made substantial strides in improving their efficiency. One direction we've focused on is the development of highly optimized protocols for specific important problems, like reporting queries (what value is stored in memory location x of my database?), matrix multiplication, graph problems like perfect matching, and certain kinds of linear programs. Many of these are provably optimal in terms of space and communication costs, consist of a single message from the cloud to Alice (which can be sent as an email attachment or posted on a website), and already save Alice considerable time and space while imposing minimal burden on the cloud, both in theory and experimentally. But for the rest of this post I will focus on *general-purpose* methods, which are capable of verifying arbitrary computations.

The high-order insights of this line of work are as follows. The statements below have precise theoretical formulations, but I'm referring to actual experimental results with a full-blown implementation. Note that a lot of engineering work went into making our implementations fast, like choosing the "right" finite field to work over, and working with the right kinds of circuits.

1) We can save Alice substantial amounts of space essentially for free. The reason is that existing interactive proof protocols (such as Interactive Proofs for Muggles by Goldwasser, Kalai, and Rothblum, which is the protocol underlying our implementation) only require Alice to store a fingerprint of the data. This fingerprint can be computed in a single, light-weight streaming pass over the input (say, while Alice uploads her data to the cloud), and serves as a sort of "secret" that Alice can use to catch the cloud in a lie. The fingerprint doesn't even depend on the computation being outsourced, so Alice doesn't need to know what computation she's interested in until well after she's seen the input, and she never needs to store the input locally.

2) Our implementation already saves Alice a lot of time relative to doing the computation herself. For example, when multiplying two 512x512 matrices, Alice requires roughly a tenth of a second to process the input, while naive matrix multiplication takes about seven times longer. And the savings increase substantially at larger input sizes (as well as when applying our implementation to more time-intensive computations than matrix multiplication) since Alice's runtime in the protocol grows roughly linearly with the input size. So I'd argue that verifiable computation is essentially a solved problem in settings where the main focus is saving Alice time, and the runtime of the cloud is of secondary importance. At least this the case for problems solvable by reasonably small-depth circuits, for which our implementation is most efficient.

3) We've come a long way in making the prover more efficient. Theoretically speaking, in our ITCS paper with Graham Cormode , we brought the runtime of the cloud down from polynomial in the size of a circuit computing the function of interest, to quasilinear in the size of the circuit. Practically speaking, a lot of work remains to be done on this aspect (for example, our single-threaded cloud implementation takes about 30 minutes to multiply two 256 x 256 matrices, and matrix multiplication is a problem well-suited to these sorts of protocols), but we are in much better shape than we were just a few years ago.

4) All of the protocols (special-purpose and general-purpose alike) are extremely amenable to parallelization on existing hardware. This holds for both Alice and the cloud (although Alice runs extremely quickly even without parallelization, see Point 1). For example, using GPUs we can bring the runtime of the cloud to < 40 seconds when multiplying two 256 x 256 matrices. Obviously this is still much slower than matrix multiplication without integrity guarantees, but we're now just one or two orders of magnitude away from undeniable usefulness.

The extended abstract  appearing in HotCloud (which should be viewed largely as an advertisement for the arxiv version) can be found here . We tried hard to give an accessible, if very high level, overview of the powerful ideas underlying interactive proofs, which I hope will be useful for researchers who are encountering verifiable computation for the first time.  Slides describing the entirety of this line of work in more detail can be found here .

I want to close by mentioning two exciting lines of work occurring in parallel with our own. First, Ben-Sasson, Chiesa, Genkin, and Tromer are working toward developing practical PCPs, or probabilistically-checkable proofs (see their new paper here ). The PCP setting is much more challenging than the interactive proof setting we have been working in above: in a PCP, there is no interaction to leverage (i.e. the cloud sends a single message to Alice), and moreover Alice is only permitted to look at *a few bits* of the proof. The latter may seem like an artificial constraint that doesn't matter in real outsourcing scenarios, but it turns out that building a practical PCP system would buy you quite a bit. This is because one can throw certain cryptographic primitives on top of a PCP system (like collision-resistant hash functions) and get a wide variety of powerful protocols, such as succinct arguments for all of NP (i.e., protocols requiring very little communication, which are secure against computationally bounded adversaries). The work of BSCGT appears to still be in the theoretical stage, but is very exciting nonetheless. Check out their paper for more details.

Second is work of Setty, McPherson, Blumberg, and Walfish, from NDSS earlier this year (see their project page here ). They implemented an argument system originally due Ishai, Kushilevitz, and Ostrovsky, and bring the runtime of the cloud down by a factor of 10^20  relative to a naive implementation (yes, I said 10^20; this again highlights the considerable engineering work that needs to be done on top of the theory to make proof or argument systems useful). Our protocols have several advantages not shared by SMBW (like security against computationally unbounded adversaries, and the ability to save the verifier time even when outsourcing a single computation), but this is another big step toward a practical implementation for verified computation. It looks like related work by Setty, Vu, Panpalia, Braun, Blumberg, and Walfish will be presented at USENIX Security 2012 as well (see the conference page here ).

The golden age for negative applications of interactive proofs and PCPs (such as hardness of approximation results) arrived over 15 years ago, and continues to this day. Perhaps the time for positive applications is now.