Some additional thoughts
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.
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.
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.
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.
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 . Knowing a bound on yields a decision procedure for any mathematical conjecture that can be coded via a -state machine checking iteratively for a counterexample; the Collatz problem gives an especially small . 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?
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]
The role of sex?
Cropped from source
Christos Papadimitriou has a joint paper with Adi Livnat, Aviad Rubinstein, Gregory Valiant, and Andrew Wan that will appear soon at FOCS 2014. The conference is October 19–21 in Philadelphia, with workshops and tutorials on the 18th. Here are the accepted papers, several others of which interest me a lot. The last parallel session on Monday afternoon before my own award lecture has three of them in one room, including a paper co-authored by my recent student Danupon Nangonkai, and three on quantum—it would be nice to be in a quantum superposition and attend both sessions.
Congratulating Dick on the 2014 Knuth Prize
Cropped from source
Dick Lipton is of course the founder and driving writer of this weblog. He is also a computer scientist with a great record of pathbreaking research. The latter has just been recognized, I am delighted and proud to say, with the award of the 2014 Knuth Prize. The prize is awarded jointly by the ACM Special Interest Group on Algorithms and Computation Theory and the IEEE Technical Committee on the Mathematical Foundations of Computing, and was instituted in 1996, shortly after the formal retirement of the great—and very much active—Donald Knuth.
Today I am glad to give my congratulations in public, and also my thanks for a wonderful and long association.
Things we did not know
|Ulam holding a strange device|
Stanislaw Ulam was a Polish-American mathematician whose work spanned many areas of both continuous and discrete mathematics. He did pioneering research in chaos theory and Monte Carlo algorithms, and also invented the concept of a measurable cardinal in set theory. His essential modification of Edward Teller’s original H-bomb design is used by nearly all the world’s thermonuclear weapons, while he co-originated the Graph Reconstruction conjecture. His name is also associated with the equally notorious 3n+1 conjecture. Thus he was involved in some strange corners of math.
Today Ken and I want to talk about some strange facts observed by Ulam and others that we did not know or fully appreciate.
A reversal question
Freeman Dyson celebrated his birthday last December. He is world famous for his work in both physics and mathematics. Dyson has proved, in work that was joint with Andrew Lenard and independent of two others, that the main reason a stack of children’s blocks doesn’t coalesce into pulp is the exclusion principle of quantum mechanics opposing gravity. He shaved a factor of off the exponent for bounds on rational approximation of algebraic irrationals, before the result was given its best-known form by Klaus Roth. He has received many honors—recently, in 2012, he was awarded the Henri Poincaré Prize at the meeting of the International Mathematical Physics Congress.
Today Ken and I want to talk about one of his relatively recent ideas, which is more mathematics than physics. Perhaps even more theory than mathematics.
See a number, make a set
Henning Bruhn and Oliver Schaudt are mathematicians or computer scientists, or both. They are currently working in Germany, but wrote their survey on the Frankl Conjecture (FC) while working together in Paris. Schaudt is also known as an inventor of successful mathematical games.
Today Ken and I wish to talk about the Frankl conjecture and a principle of mathematics. Read more…
Some algorithmic tricks were first invented in complexity theory
Andrey Kolmogorov, Fred Hennie, Richard Stearns, and Walter Savitch are all famous separately; but they have something in common. Read on, and see.