Microsoft Research source

Omer Reingold is a brilliant researcher, and now all can see that he is also a very classy and thoughtful person. As you all know by now, he and many others have suddenly lost their jobs with the closing of Microsoft’s Silicon Valley Campus (SVC) Research Lab. The lab closed this week: it has been removed from Microsoft’s “Research labs worldwide” page. The closing affects about 50 jobs directly, and is part of an overall reduction of about 18,000 staff worldwide.

Today, Ken and I wish to express some of our feelings about this. At first we thought we could not add to what others have already said about the closing, but we realized we could still express support and add to the wider conversation.

Omer is among fourteen listed writers of the “Windows on Theory” blog, all affiliated with Microsoft Research. He wrote a short and classy post on the blog. My former student Parikshit Gopalan, who was at the lab and is now affiliated with a group in Redmond, added a similar comment, among many in the post. Omer and Parikshit wrote a nice paper in FOCS 2012 with Raghu Meka, Luca Trevisan, and Salil Vadhan, on new ways to construct pseudorandom generators. We covered it briefly two years ago.

Parikshit also writes for the blog—here is a nice post on crisply-stated open problems involving alphabet size in coding theory. In his comment last weekend he reflected:

History tells us that research labs are mortal. Like mortals, they are finally judged by their accomplishments rather than their longevity.

Judging the value of accomplishments, however, is often a longer-term process than “longevity,” and that plays into some of our thoughts.

## Some Thoughts

${\bullet }$ We are not shocked. Luca Trevisan wrote a very thoughtful piece on his own blog, “in theory.” His piece started with:

I am still in shock at the news that Microsoft decided to shut down MSR SVC and fire, literally from one day to the next, almost all the scientific staff.

I, Dick, am not so shocked; I will explain in detail why in a moment.

${\bullet }$ We are very impressed by comments from some of the researchers. Not just Omer but many others affected and not. I think this is something that we can find heartening.

${\bullet }$ We are happy to hear about the community response. Luca wrote:

Here at Berkeley and Stanford we will do our best to help, and we will make sure that everybody has some space to work. There will also be some kind of community-wide response, but it will take some time to figure out what we can do. Meanwhile, I urge everybody to reach out to their friends formerly at MSR SVC, make them feel the love of their community, and connect them to opportunities for both short term and long term positions, as they weigh their options.

We are very happy to hear this, and we add that other institutions will also try and help any that need it. Of course being far away makes it less likely that some of us can help immediately. But I personally will try to get help from Tech for any that need it.

${\bullet }$ Probably no personal judgment. In academia with tenure cases etc., all judgment is personal—when cuts are on a larger scale, there is invariably protest which is often effective, as some commenters have noted. In a post three years ago on how research is like the stock market and “failure must be an option,” Ken inserted a note on his father’s recollection of the “Terrible Twenty.” This name for recipients of annual AT&T and/or IBM lab fellowships spoke the ethic that the company needed only a few to succeed to be golden. SVC was far from a case of going 0-for-20; highly profitable work has been documented coming from there. So it was probably a larger personnel matter, not a personal one, and this is far from unusual in big business.

 “Windows on Theory” team source

## Why Not Shocked

I have been around a while and have seen labs come and go over the years. I can still remember when AT&T Bell Labs was the greatest lab in the world; it still is strong, but once was the lab. One of the reasons for this was simple: its parent company was a monopoly. It had an immense amount of cash and could afford to have researchers that did whatever they wanted. For example, for years Shin Lin, a Bell Labs researcher, worked on the Busy Beaver Problem.

A busy beaver function quantifies these upper limits on a given measure, and is a noncomputable function. In fact, a busy beaver function can be shown to grow faster asymptotically than does any computable function. The concept was first introduced by Tibor Radó as the “busy beaver game” in his 1962 paper, “On Non-Computable Functions.”

Ron Graham was the director of the mathematics division which hired Lin, who was Radó’s student. Ron told me that each year he had to argue with upper management to keep Lin. Finally in 1970, Lin with Brian Kernighan found a brilliant algorithm for cutting graphs. This algorithm and its descendants has been used now for decades to approximate everything from VLSI layouts to the Traveling Salesman Problem. If Bell Labs had not kept Lin around, perhaps this algorithm would still exist, but perhaps not. Or maybe its discovery would have been delayed for decades. Who knows.

So, finally, here are two reasons I am not shocked, beyond factoring in that this is just the tip of a global 14% iceberg of layoffs that shows in our field. First, in my opinion, the ability for companies to support very far out research is sensitively linked to exigencies of their cash flow. Microsoft is being pressed by the shift from PC’s as the main platform—where they had an almost monopoly on the OS—to a place where there are many players in the mobile world. This means that they are less able to support research of an open kind. Second, even in times of good cash flow, whether from monopoly or booms, people had to fight to keep good people. One of my friends opined that in the levels below recent personnel changes at the top, no senior swingman at Microsoft was able “to set priorities for investments that will not mature in ten years.”

This does not let Microsoft off the hook. They could have handled the closure better. Well, perhaps better.

Let’s not let Ken off the hook either—he writes the rest of this post, besides his having written some of what’s above.

## Mining Value and Beavering Away

Some commenters have alluded to Microsoft’s recently spending 2.5 billion dollars in cash to acquire the Minecraft computer game. My kids—this is Ken—and their cousins have all been avid players. Unlike most video games—most games, period—its prime value is open-ended creativity. It can be played as a survival game, and servers can be set up to provide battle competitions, but this is secondary. The ethic is creative enjoyment and sharing. A question that was percolating even before the sale is how far players can monetize servers and other content they create.

In essence all of our community, in academia and industry both, have been engaged in a game of “Mindcraft” in which monetization and even practicality are not the prime movers. Perhaps the best-known testament upholding this is Godfrey Hardy’s 1940 essay, “A Mathematician’s Apology.” In this he famously stated that whole branches of mathematics including number theory were “useless,” especially for any “warlike purpose”—and he was instantly proved wrong by the use of number theory to break cryptosystems, to say nothing of creating them. The point we offer, for conversations such as those in Scott Aaronson’s item and comments, is not to say what is or proves to be valuable, but rather the sheer problem of judging—of projecting an appraisal:

What distinguishes “academic” research—in industry also—is undertaking creation that is not predicated on knowing, or even the possibility of judging, its extrinsic value.

Of course academics has institutions for judging intrinsic value by standards of research. By those there is no doubt about the salience of the “Busy Beaver” function ${B}$. Knowing a bound on ${B(k)}$ yields a decision procedure for any mathematical conjecture that can be coded via a ${k}$-state machine checking iteratively for a counterexample; the Collatz problem gives an especially small ${k}$. As the bibliography of Wikipedia’s BB page shows, academic interest has remained high. But let us notch up the moral of Dick’s story above by asking, what about its possible extrinsic value? BB programs are extreme cases for the generally important task of predicting and verifying program behavior. A recent essay by Liesbeth de Mol makes a connection to computer-assisted proving.

Even with something as globally profitable and understood as the open-source ethic, projecting value is hard—including its strategic competitive value to large sponsors. This partly owes to the difficulty of proving a negative, such as the cost of avoided bugs.

Here’s a silly but simpler example from my chess research. Despite near-universal belief in the chess community that the ratings of top players today are “inflated” by over 100 points compared to the 1970s and 1980s, my work shows that the implementation of the Elo rating system by the World Chess Federation (FIDE) has been remarkably stable from the beginning. A 30-point effect that can be more readily ascribed to progressively faster time controls since the early 1990s seems recently to have reversed. FIDE lists over 400,000 rated players, who pay fees of some tens of dollars per year to national federations under FIDE’s auspices for this and other services. Is knowing this integrity of ratings worth 50 cents per player? On the flip side of “judging a negative,” how much is saved by providing resistance to any impulse to fix something that isn’t broken? I may earn compensation for other aspects of my work, but how could one judge to monetize this aspect?

## Open Problems

In summary, our thoughts go to all those affected by the closing and we wish all the best in the near and far future.

[name and word fixes]

1. September 27, 2014 10:22 pm

I remember when a similar thing happened with EDS …

2. September 27, 2014 10:46 pm

am maybe one of worlds biggest fans of busy beaver research, having written on it on my blog and actually engaged in it personally, but have to admit, that it really is hard to justify as having any value to Bell labs. so we’re facing a bigger problem of how society figures out how to fund worthwhile social “services” such as science etc and its a bigger challenge than corporations can figure out how to solve. maybe its a moment to reflect that “corporations are not the answer to everything” and esp as govts fall down, that will become a more apparent fact. also note coupland just wrote a great article/ retrospective on whats left of bell labs. that link and more in ms Silicon Valley research lab shuts down, easy come, easy go

• September 28, 2014 12:15 am

Thanks; I did read your post among much else—yours was one of “those alluding to Minecraft”. There are rarefied connections between BB and proofs in formal systems. The question on “value” for me is whether something like Homotopy Type Theory will make them less so. HoTT seems to have interest at Bell Labs and/or Lucent now; maybe the impression comes most from their proximity to IAS. I mulled saying more about the role of synergy in realizing value, and work being “too early”, but others have addressed this and the section was already long enough.

3. September 28, 2014 10:02 am

Totally agree about the fact that research labs are mortal. It happens from time to time that one Lab has so much funding and they carry on for a few years. Then, their parent companies realize they have contributed to research but they haven’t done anything making profits for them. So, they decide to shut it down. I heard that even Leslie Lamport(winner of the prestigious ACM Turing Award) is going to be laid off. This might look like a cruel act from Microsoft(my ex-boss), but this has happened in the past, is happening in the present and will continue to happen in the future.

September 28, 2014 1:02 pm

Leslie Lamport is not getting laid off. He is one of the few retained.

5. September 28, 2014 9:05 pm

@Anon – Oh. Great. I would have been really disappointed if he had been laid off.