And Thanks for All the Fish, Altavista Version

All sorts of news about the plug finally being pulled on Altavista, which I still have an attachment to, being partially the product myself of DEC.  Here's a nice eulogy.  There's a good basic history at wikipedia's Altavista page. 

The book The Search: How Google and Its Rivals Rewrote the Rules of Business and Transformed Our Culture (mostly about Google, but covers other history as well) probably sums up Altavista's history as well as anything:

The mighty rise and fall with spectacular regularity int his business, and the pace of boom and bust only increased as the Internet took root in the mid-1990s.  Yet Altavista is remarkable for a number of reasons.  To borrow from the present, Altavista was the Google if its era.  In 1996, it was arguably the best and most-loved brand on the Web.  It presaged many of the current innovations and opportunities in search, from automatic language translation to audio and video search to clustering of results.  And as a business Altavista attempted -- and failed -- to go public three times in three short years under three different owners.  Possibly most instructive, Altavista was the product of a company that was an extraordinary success in its original business but ultimately failed because of hidebound management unwilling to drive by anything other than the rearview mirror. 

And Thanks For All the Fish

As my Area Administrator Tristen reminded me, "...today is officially your last day as my boss..."  Monday is July 1, which officially ends my term as Area Dean for Computer Science at Harvard.  The indefatigable David Parkes will be taking on the position.  (Thank you, David!  And my condolences!) 

While a ponderous exposition of all the wonderful things that have happened in Harvard CS is clearly called for, I'll try to keep it brief.  My main goal in taking the job was to turn our small group into a somewhat larger group, and I feel that has gone well.  We've hired five new excellent faculty over the last 3 years (Ryan Adams, Eddie Kohler, Jelani Nelson, Yaron Singer, and Stratos Idreos).  We've also done well in promotions, including multiple successful tenure cases, which was the other really important part of my job.  In other news, CS enrollments at Harvard are still booming, and while credit for that certainly belongs to others (a shout-out here to David Malan, who keeps bringing more and more students into our intro CS 50 course somehow), as Area Dean, I consider it my job to take credit for it.  (Similarly, while I'm at it, I'll take some credit for Les Valiant finally winning his long-deserved Turing award!)  Our faculty, who have always been friendly, cooperative, and worked together well continue to do so.  So I didn't break anything there (which is probably as good summary as any of my past three years).  My job was really to be a buffer with other administration so the rest of the faculty could go about their business being as great as they are.  And, as I've said, then taking a share of the credit for their greatness afterwards.  

I've already thanked all the faculty for putting up with me the last few years.  But special thanks goes to my Administator Tristen Dixey, who insists on calling me "boss" even though it's quite clearly more correct the other way around.  She makes CS at Harvard go.  And while all the faculty are always helpful, I very frequently leaned on the trio of Harry Lewis, Greg Morrisett, and Margo Seltzer for Area Dean advice, to make sure I didn't do anything too stupid.

Other thanks go to my graduate students -- both Zhenming Liu and Giorgos Zervas who previously graduated, and Justin Thaler this year -- for keeping me involved in (their) research.  (And all my other collaborators as well, but my students especially.)  Sorry you had to put up with me administrating while you were busy doing the work for graduating.   

It's hard to believe it's been three years.  I imagine someday I may find myself taking on another administrative position.  But for now, it's a nice feeling just to be done with this one.  

How Should We Choose Students?

Some of my previous posts have led me to think about the following -- something I'm hoping to write a longer piece about in the near future.

In the past few weeks, at Harvard (and elsewhere) there have been reports about the "decline of the humanities".  (Whether these reports have any significant bearing in reality is not necessarily important to this post.)  But machine learning keeps getting better and better.  While we may never be able to predict the exact outcome for an individual student, statistically speaking, as the universities gather more data, they will get better at predicting, for example, what a student will major in.  Potentially, with the right sort of tracking, universities may be able to predict reasonably well what jobs students may go into -- heck, they may get a statistically meaningful prediction of their future net worth.*  In particular, if we wanted to choose students according to what they were going to major in, in order to keep the humanities supporters happy, we could;  while we can already kind of do that now (based on, for example, what student say they want to major in), we'll just keep getting better at it.

This will lead to all sorts of questions.  Or, perhaps better said, will make the questions that already to some extent exist more pronounced.  First, getting to to the humanities concern, how should we choose our students?  Should we have quotas by future major?  We could assign departments a permanent percentage (well, an "expected percentage") of the incoming graduates and accept students accordingly?  From some faculty members' and administrators' point of view, perhaps this makes sense;  we can guarantee a department size, and a suitable faculty/student ratio per department.  To me, it seems potentially disastrous, turning the university into a static entity, which perhaps would not in any sense limit any individual student in terms of what they want to study, but would create a less flexible global atmosphere.  Again, in some sense, this question exists today;  at least some people have responded to the "humanities crisis" by saying that how students are accepted should be changed (to give preference to humanities-interested students), but the question becomes an even more significant challenge once you assume you actually have very strong prediction methods that can allow you to select students in this way more accurately than has been the historical norm.   

Of course, going beyond the picayune issue of whether we should choose students according to what they might major in, there's the larger scale question of how we should choose students.  Indeed, this question lies at the heart of many an affirmative action lawsuit, with the "reverse affirmative action" side claiming that people of what I will call "white" descent are not admitted in favor of less qualified "non-white" students.  (The issue is obviously more complicated than this paragraph can do justice to;  for example, the issue of Asian American discrimination arises.)  In such discussions, one generally hears the term "merit" -- if only schools just took the top people according to merit and ignored race completely -- but what exactly is merit?  Legislators or judges seem to want some sort of formula (usually based on grades and or test scores -- except that, by studying their own big data, some at Google claim that "G.P.A.'s are worthless" for their hiring).  Let's suppose our machine learning tools are good enough to estimate merit quite accurately if we define the merit objective function for them.**  How should we define it?  One particularly intriguing question, is the "merit" of the class simply the sum of merits of the collected individuals -- in which case we should ignore things like what major they want to choose -- or is the merit of the sum different from the sum of the merits?  I have some of my own not-completely-worked-out ideas, but again, this seems worth writing a longer essay about to work through the possibilities and implications.  

A further interesting question that arises is what sort of information can and should universities gather about applicants, in order to make these predictions.  College applications already ask for a lot -- grades, lists of activities, essays, letters of recommendation, test scores, sometimes interviews.  Suppose, though, that we could much more clearly predict your "merit" as a future student by parsing your Facebook account, or better yet, your e-mail from the last 3 years.  Should we be able to ask for that?  Perhaps we can guarantee that our algorithms will return a score only and your actual e-mail will not be examined at all by any human beings.  Or, by the time we get to the point where our machine learning algorithms are ready for that data, privacy won't matter to anyone anyway, especially if providing access to the data is needed to get into their choice of school. 

In some sense, none of these questions are inherently new.  But they appear to become different in kind once you think about the power machine learning will give to systems that make decisions about things like who goes to what university.  While the university setting is arguably small, the themes seem quite large, and perhaps the university is the place where some of the thinking behind the larger themes needs to be taking place.  And taking place now, before the technology is here and being used without a lot of thought into how it really should be used.

* Obviously, there are countless other potentially more significant uses of machine learning technology.  But I work at a university, so this is what has come to mind recently.   

** As far as I know, the merit function for Harvard is not "how much will you or your family donate to Harvard in the future".  But it could be.  Even if we avoid the potential self-interest of universities, to what extent is net worth a suitable metric of merit?  I was an undergraduate at Harvard and am now a professor there;  Bill Gates was an undergraduate (who notoriously dropped out) and donated a large amount of money for the building I now work in, and apparently has had a few other successes.  Extreme cases, to be sure, but how would the merit objective function judge these outcomes?  

Valiant's Book Out: Probably Approximately Correct

Les Valiant has a new book out: 
Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World

I was sent a free copy last week, but was delayed in reading it due to my avocational vocation.  (I was "talking with lawyers" a bunch.)  But I wanted to make sure to finish it over the weekend.  And now I'll recommend it all to you.

It would be, I think, somewhat inappropriate for me to attempt to review the book, but I'll aim to give some description of it which may encourage you to purchase it.  The book is aptly summarized by the following two sentences from it.

"The focus here will be the unified study of the mechanisms of evolution, learning, and intelligence using the methods of computer science."

"By the end of the book I hope to have persuaded the reader that when seeking to understand the fundamental character of life, learning algorithms are good place to start."  

Needless to say, the book is ambitious in scope, what one might expect from a Turing award winner, but in particular from Les.  If you have heard his Turing award lecture (available here), you can think of it as a preview of the book.  It is hard not to read the book as a challenge, to computer science in particular, but to the sciences more generally.  It is a call to arms, a vision, a plea, an agenda.

Because of this, I would recommend it highly to all computer scientists (in any area).

I would also recommend to it all scientists, so they could see this clearly laid out research vision from one of the leaders in computer science -- and, arguably, the one who is most interested in promoting the extension of the theory of computation to other sciences.  It might, I think, spur them to consider the relationship between computing and their own area of work, even if they are not directly working on evolution, learning, or intelligence.

It is slightly harder to recommend it to a general audience.  The book tackles fundamental questions of the connections between life and computation, making it a philosophical work certainly worthy of a large and general audience.  It raises some quite deep questions about the nature of human thought from what I think for most would be a novel vantage point.  But it does not shy away from the technical, and while, as promised, "The language of mathematics will be used, but only a little, and will be explained where used.", I imagine readers without a math/computer science background could get lost at times.  Still, other technical books (e.g., anything by Lisa Randall) find a large audience, so perhaps I underestimate the population at large. 

A final personal aside:  because I work with Les, when I read it, it came out in his voice.  I think the book very much sounds like Les -- it reads, to me, like him speaking -- but perhaps that's a trick of my own mind.  

Harvard Humanities

There's been a mild hubbub toward the end of the week here, due to a report and some articles (Boston Globe, WSJ) that the number of students majoring at the humanities at Harvard is in decline.  (See also this post at Shots in the Dark.)

Happily, this appears to be much ado about nothing.  Ben Schmidt at Princeton has already run the nationwide number, and shown that the decline is really more about a bubble in the 1960's of humanities majors.  Which just goes to show, when looking at historical data, what starting point you choose is important.  (Yes, that goes in the "duh", "lies, damn lies, and statistics" category.)

At Harvard, specifically, there are a variety of potential reasons for this trend, including but not limited to the general national trend.  In computer science, we've been actively trying to attract and retain students;  the humanities just may be facing more competition.  There is some claim that Harvard's financial aid policy is having an effect;  to the extent that students are coming from less well-off backgrounds, they may be seeking an education that they feel more directly will lead to job prospects.

There has been, however, perhaps a hint (or more than a hint) in some of all of what's going around that somehow people focusing on things outside of the humanities is "anti-intellectual", with students caring more about immediate job prospects than, well, the "intellectual" humanities. 

Naturally, I resent this.  I find computer science has a very solid intellectual basis.  The nature of computation, what it means to compute efficiently, how computing is found throughout nature (more on this in my next post) -- there's a lot interesting intellectually there.  If one seeks more "moral" sorts of lessons, I think many can naturally be found throughout CS, with the right interpretation.  The challenge of tradeoffs, for instance, is an underlying concept of my own algorithms class, and certainly appeared (if less quantitatively) in the moral reasoning class I took as an undergraduate. 

On the other hand, I understand where this is coming from.  There is a sense that the humanities is under siege (particularly at state institutions);  there are politicians of the mindset that "if it's not job training, why are we providing it?"  I believe that one should study more than computer science to learn to be a more complete human being;  I am thrilled to be at an institution where history, English, religious studies, as well as Romance languages, economics, and government are studied.  When one feels under attack, one's reactions might seem a bit more extreme.   

I'm not one to say where the final balance will be, or should be.  I do believe an understanding of computation should be a fundamental part of a liberal arts education;  it is clearly one of the most powerful ideas of the last century.  And it's our goal to make it both so that every Harvard student feels welcome and able to take a computer science course, and so that many understand our excitement and choose to major in it.  For a few decades, Harvard has been a bit behind in the role computer science has played at the university, and I think now that's changed.  So to the extent that the humanities feel the competition is from us, well, I'm actually all for it.    

Thanks to Harry Lewis for various discussions on this theme.  

NSF Reviewing Trial Run

Noam Nisan points to the NSF trying out some new rules for reviewing in its upcoming SSS program. 

There's a lot here to discuss.  First, I'm glad to see the NSF is willing to try out some new reviewing approaches.  They've been using the same approach for a long time now (1 or 2 day in person meetings, a reviewer panel drawn according to who is available and willing);  I really haven't seen any discussion from the NSF as to why it's a good review system, and it's typically got some major cons (as well as, admittedly, some pros).  But as far as I know -- and perhaps some people are more knowledgeable than I am on the topic -- it's not clear at all to me why it's become the stable equilibrium point as a reviewing method.

That being said, there's some clear pros and cons to this experiment.  Some features + initial off-the-cuff commentary.

1.  No panel review.  Proposals will be split into groups of 25-40, and PIs in the group will have to review other proposals (they say 7 here) in that group.  [If there are multiple PIs on a proposal, one has to be the sacrificial lamb and take on the role of reviewer for the team.]   

I kind of like the idea that people submitting proposals have to review.  One of the big problems in the conference/journal system is that there's minimal "incentive" to review.  Good citizens pay back into the system.  Bad citizens don't.  This method handles the problem in a natural way -- you submit, you review.  There are many potential problems with this method to be sure (as we'll see in the proposed implementation below).

2.  A composite ranking will be determined, and then the "quality" of the reviews of the PIs will be judged against this composite;  then the PIs ranking may be adjusted according to the quality of their reviews.

Ugh.  Hunh?  I get the motivation here.  You've now forced people into doing reviews, who may not want to.  So you need an incentive to get them to do the reviews, and do them well.  One incentive is that if you're late in your reviews, your own proposal will be disqualified.  That seems fine to me.  But this seems --- off.  I should note, they have a whole subsection in the document labelled

Theoretical Basis:

The theoretical basis for the proposed review process lies in an area of mathematics referred to as mechanism design or, alternatively, reverse game theory.  In mathematics, a game is defined as any interaction among two or more people.  The purpose of mechanism design is to enable one to “design” the “mechanism,” namely the game, to obtain the desired result, in this case to efficiently obtain high-quality proposal review while providing the advantages noted above.  In mechanism design, this is done by formulating a set of incentives that drive behavior in the desired direction.  The mechanism presented here was devised by Michael Merrifield and Donald Saari [¹].

I suppose I now have to go read the Merrifeld and Saari paper to see if they can convince me this a good idea.  But before reading that, there are multiple things I don't like about this.

a)   Why is "reviewer quality" now going to be part of how we make decisions about what gets funded?  I'm not sure to what extent, if any, I want "reviewer quality" determining who gets money to do research.  Here's what the document says:

To promote diligence and honesty in the ranking process, PIs are given a bonus for doing a good job.  The bonus consists of moving their proposals up in the ranking in accordance with the accuracy with which their ranking agrees with the global ranking.  This movement will be sufficient to provide a strong incentive to reviewers to do a good job, but not large enough to severely distort the ranking merely as a result of the review process.  Recognizing that, if all reviewers do an excellent job of ranking the proposals they review, all PIs’ proposals will be moved up equally, which means that the ranking will not be changed, the maximum incentive bonus will be a movement of two positions, that is, a proposal could be moved up in the ranking to a position above the next two higher proposals.

With funding ratios at about 15% (I don't know what the latest is, but that seems in the ballpark), two places could be a big deal in the rankings.  

b)   Why is there the assumption that the group ranking is the "right" score -- particularly with such small samples?  I should note I've been on NSF panels where I felt I knew much better than the other people in the room what were the best proposals.  (Others can judge their confidence in whether I was likely to have been right or not.)  One of the pluses of face-to-face meetings is that a lone dissenter has a chance to convince other reviewers that they were, well, initially wrong (and this happens non-trivially often).  I'm not sure why review quality is judged by "matching the global ranking".

c)   Indeed, this seems to me to create all sorts of game theoretic problems;  my goal in reviewing does not seem to be to present my actual opinion of a paper, but to present my belief about how other reviewers will opine about the paper.  My experience suggests that this does not lead to the best reviews.  The NSF document says:

Each PI will then review the assigned subset of m proposals, providing a detailed written review and score (Poor-to-Excellent) for each, and rank order the proposals in his/her subset, placing the proposals in the order which he/she thinks the group as a whole will rank them, not in the order of his/her personal preference.

But then it says:

Each individual PI’s rankings will be compared to the global ranking, and the PI’s ranking will be adjusted in accordance with the degree to which his/her ranking matches the global ranking.  This adjustment provides an incentive to each PI to make an honest and thorough assessment of the proposals to which they are assigned as failure to do so results in the PI placing himself/herself at a disadvantage compared to others in the group.

So I'm saying I'm not clear myself how their incentive system -- based on the global ranking --- gives an incentive to make an honest and thorough assessment.  Even the document itself seems to contradict itself here.

d)  This methodology seems ripe for abuse via collusion -- which is of course against the rules:

The PIs are not permitted to communicate with each other regarding this process or a proposal’s content, and they are not informed of who is reviewing their proposals.

But offhand I see plenty of opportunities for gaming the system....

e)  This scheme is complicated.  You have to read the document to get all the details.  If it takes what seems to be a couple of pages to explain the rules of the assignment and scoring system, maybe the system is too complicated for its own good.

That came out pretty negative.  Again, I like the idea of experimenting with the review process.  I like the idea that submitters review.  I understand the concept that we somehow want to incentivize good reviews, and that's very difficult to incentivize.

This actual implementation... well, I'd love to hear other people argue why it's a good one.  And I'd certainly like to hear what people think of it after it's all done.  But it looks like the wrong way to go to me.  Maybe in the morning, with some time to think about it, and with some comments from people, it will look better to me.  Or maybe, after others' comments, it will seem even worse.  

Review are In, 2013

Teaching reviews are in!  I'm happy to say students were more forgiving than last year.  But also, I notice in the reviews the effects of 4 significant changes from last year.   (The best is saved for last.)

1.  Students knew it was my last year teaching the course.  I think they were nicer to me than normal because of it.  (Pity points!)

2.  For the last several years, students have complained that the midterm coincided with "Housing Day", the day the freshmen find out about where they'll spend their later years, and apparently it's a big party day.  This year, I was able to move the midterm.  (For didactic reasons, I assure you -- some of basic material in my course is now covered in an earlier class, saving me a lecture early in the semester.)  Students really appreciated that.  (I maintain that my midterm being the Thursday before finals precedes the advent of "Housing Day" -- someone put Housing Day on the day of my midterm, not the other way around -- but students have not sympathized with this reasoning.) 

3.  This was the first year students had the advantage of taking that new class, CS20, designed to give them more background on CS mathematics.  (We finally have the CS "Discrete Math" class we haven't had but have probably needed.)  I think this helped students, especially at the lower tail, and probably somewhat helped review scores.

4.  The final change may arguably be the most important.  In the past I've given longer assignments over usually 2 week periods;  something like 7-9 problems.  At the urging of one of my experienced TAs, who both wanted the grading split up more and thought the students would prefer it, I broke up the problem sets, so they were due weekly, and were usually 4 or 5 problems.  The feedback from many students was that they liked this approach better (obviously not from direct experience with the class previously, but from what they had heard from other students).

To me, this remains counterintuitive.  The students were getting the same problems either way, so the splitting only added an additional constraint on them.  Instead of having eight problems over two weeks, they were forced to do the first four in week one and the next four in week two.  But, clearly, for psychological reasons many students want (need?) that constraint.  As some have explained to me, they aren't going to start the assignment until they're close to the deadline, so the additional deadline prevents them from becoming overloaded and overstressed by a longer assignment.  Perhaps, beyond the psychology, part of the issue may be student collaboration -- more frequent shorter assignments introduces constraints that probably help encourage scheduling of working together.   

I worry about the time management skills of Harvard students.  Or I suppose for many it's just the way they live -- their schedules constantly packed full with deadlines serving as the basis for their priority scheduling.  I hope they experience a different lifestyle at some point.

However, lessons learned for whatever undergrad class I teach next!  Short weekly assignments.  And be sure to avoid student (non-academic) events when setting up the midterm in the class schedule.

Finally, I still suspect my reviews would be non-trivially better if they happened after grades were out.  Students often think they're doing worse than they are -- they don't see how much the curve helps them.  For example, one senior, after the final, came up to me worried that he/she did poorly enough that he/she would fail the class.  I asked how he/she had done over the semester, and said it seemed very unlikely, but I'd send mail after grading the final.  The student got a C and was in absolutely no danger of failing.  The horror stories of CS124 have been somewhat exaggerated over time -- perhaps all the more reason a "refresh" is in order.  

Anyhow, thanks again to this year's CS 124 class -- for those of you who aren't graduating, I hope to see you around, and for all the students, if you've read this far, I hope you'll send me stories when you find whatever you learned in CS 124 to be useful to you. 


      

An Unusual CS Student Blog

As I'm up working/watching a Memorial Day weekend Arrested Development marathon (OK, I'm not working that hard), I found myself wandering over to Justine Bateman's blog.  Like many teens at that time period, I surely had a crush on her during her run on Family Ties.  So I had noticed that last year she had decided to go back to school to study computer science (UCLA -- college to the stars-interested-in-math-and-science, apparently;  I'm talking about you Mayim Blalik and Danica McKellar!).  But I hadn't been reading the blog.  And it's very entertaining, if only because it sounds like a freshman college blog, albeit occasionally with some pointers you might not normally find (like interviews for LA magazines).    This post, about finishing up a big project (making a computer Battleship game), is really familiar to me in tone;  I hear stuff like this from students all the time (and, of course, lived through it myself as an undergraduate). 

The point here -- besides that I now watch and have always watched too much TV -- is that computer science is awesome.*  Awesome enough that a big star of the 1980s has gotten inspired enough to go back to school and learn how to program Battleship, and more.

*And I guess another lesson is that Justine Bateman is awesome too.  Not that she'll ever see this, but Justine -- best of luck to you sophomore year and beyond!   

Grades In

The grades are in for CS 124.  Hooray!

Interesting trend : freshmen, who make up a small fraction of the class, are highly over-represented in the A and A- grades.  This has been happening for some years now. 
Extension of the interesting trend : women freshmen*, who make up a smaller fraction of the class, are even more highly over-represented in the A and A- grades.

I'd be very excited if I were teaching the class again next year -- finding undergraduates who have the potential to be TAs for multiple years is golden -- but I'll be sure to pass the names on to the new guy.**

Other side of the trend :  2nd semester seniors performed substantially below average this year.
But on the positive side :  nobody did so badly they won't graduate.  (At least, not in my class.)  

Getting grades in really makes the class feel over.  Onto summer work!  (Research and writing...)

* Freshwomen if you prefer.
** And any freshman or sophomore in the class who got an A and is interested in TAing should let me know next November or so.

Congratulations to Justin and Jon

Justin Thaler and Jon Ullman had back-to-back thesis defenses today.  Both talks were excellent -- Justin's on his work on verification methods (for cloud computing), and Jon on his work on differential privacy.  While there is still some small paperwork matters (like the actual theses to turn in), I think we should start calling them Doctor Thaler and and Doctor Ullman, just so they start getting used to it.

Congratulations Justin and Jon!

Calling Out Stupidity

While I greatly enjoy working at Harvard, there are many painfully stupid things said and done by people here -- as I suppose is the case anywhere -- that either I don't feel merit commenting on or I don't feel it's appropriate to comment on.  (And, of course, I'm sure that sometime in the past I've done or said things that others find stupid, and I'm very happy they aren't blogged about.)

However, the recent comments by Niall Ferguson are out in the public, and so over-the-top stupid that even he quickly realized how stupid they were.  And I think it's important to point out, prominently, how stupid they are, because the idea that either childless people or gay people somehow have a discounted view of the importance of the future deeply offends me, and somehow the idea that someone prominent in my workplace would say (or believe, or say in stupidity without really believing) such a thing has made my week substantially sadder.  And so I feel the need to point it out, ideally not to sadden anyone reading this, but to emphasize how sad and stupid the comments were.   

A Boy and His Atom

Some researchers at IBM are so good at playing with atoms, they decided to make a movie (called A Boy and His Atom), by moving atoms.  Cool stuff.  Computer science connections:  implications for storage.  Personal connection:  the spouse of the scientist leading the group who made the video is a friend from high school. 

Some Recent Books

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

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

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

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


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

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



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

Thanks for the Memories....

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

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

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

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

Guest Post by Mark Bun and Justin Thaler

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

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

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

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

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

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

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

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

min \epsilon

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

c_S in \mathbb{R}

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

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

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

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

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

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

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

Congratulations to Mark Bun and Justin Thaler

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

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

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

  

Guest Post by Mikkel Thorup : Results vs. Techniques

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


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

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

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

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

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

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

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

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

Upcoming Events

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

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

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

Harvard E-Mail, Again

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

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

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

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

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

Anyhow, seems like progress.

Harvard in the NCAA Tournament

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