the new theorymatters

The site has been redesigned as a blog. Watch it for informations about funding, jobs, and other stuff from the committee for the advancement of theoretical computer science.


Guest post by Oded Goldreich II

[Oded Goldreich has written a new essay, which he summarizes in the guest post below. Oded looks at the distinction between “primary” and “secondary” accomplishments, that is between doing good stuff and receiving “awards”, where “award” should be taken broadly to mean something that is given after a competition that has no other purpose than choosing a winner. Oded points to the negative effects of having important decisions, e.g. about jobs, funding and promotions, be based on “secondary” rather than “primary” accomplishments, because it pushes researchers to optimize the former, which is not good for anybody. This is a broad problem with “secondary” metrics, e.g. when schools are evaluated based on test scores or police departments based on crime statistics. (I assume we have all watched The Wire.) Oded concludes that we should abolish “awards” whenever possible; I disagree with this conclusion and I will write about it in the comments. L.T.]

The purpose of this post is to call your attention to my essay “On Struggle and Competition in Scientific Fields”, which is available from the web-page

The current essay is only remotely related to my essay “On the status of intellectual values in TOC”. So I do hope that those who misunderstood and/or disagreed with the prior essay will not hold this against the current one.

The current essay is pivoted at notions such as achievement, importance, and competition. It addresses question such as the following ones. What is the difference between struggling for achievements and competing for success? What is the effect of competitions on a scientific field? What are the specific implications on TOC?

Of course, my issue is not with the semantics of (the colloquial meaning of) the forgoing words, but rather with fundamentally different situations which can be identified by referring to these words.

Loosely speaking, by struggle I mean an inherent conflict between different people who attempt to achieve various goals and positions relative to a given setting. That is, the achievements determine the outcome of the struggle. In contrast, by competitions I mean artificial constructs that are defined on top of the basic setting, while not being inherent to it, and success typically refer to winning these competitions. That is, success is determined by the outcome of the competition.

Of course, once these competitions are introduced, the setting changes; that is, a new setting is constructed in which these competitions are an inherent part. Still, in some cases — most notably in scientific fields, one may articulate in what sense the original (or basic) setting is better that the modified setting (i.e., the setting modified by competitions). These issues as well as related ones are the topic of the current essay.

The core of the essay is Section 2.1, which provides a theoretical framework in which all these notions are discussed. This framework is used in Sections 2.2 and 2.3, which revisit familiar issues such as the evolution of the FOCS/STOC conferences, the effects of awards, and why is excessive competition bad. In particular, I trace several negative social phenomena in TOC to the growing dominance of various competitions in TOC. In Section 3, I discuss the possibility of reversing the course of this evolution and reducing the dominance of competitions in TOC.

Indeed, I have expressed similar opinions regarding the evolution of FOCS/STOC and awards in the past, but I feel that the framework presented in Section 2.1 provides a better articulation of these opinions as well as a wider perspective on them. Actually, my first, initial, and most important goal in writing this essay is to clarify to myself and to other interested readers a few issues that are quite central to our professional life. My hope that I may contribute to a change in hearts, and then to a change in reality, only comes second.

Oded Goldreich

The next Women in Theory Workshop

[I am happy to relay this announcement from Shubhangi Saraf, Lisa Zhang, Moses Charikar and Tal Rabin]

Calling all Women PhD Students (and a few undergrads)

We will be having our bi-annual Women in Theory (WIT) Workshop this year in Princeton.

The dates are June 23-27, 2012.

Applications are due on: Feb 29, 2012.

Go to: for all the relevant information.

Is the British government hiring Italian political consultant?

David Willetts, the British minister for higher education, has recently announced that the government was “inviting proposals for a new type of university with a focus on science and technology and on postgraduates.” The NYT article on the matter may be biased, but it looks like this announcement could have come from the Italian ministry of university and research, and I mean it as an offense.

So, how much will the government invest in this new university? “There will be no additional government funding,” Mr. Willetss says, and all the funding will have to come from the private sector. And what is the government’s vision and plan for this new university? Mr. Willetts says that “We are not intending to issue any guidelines. We want people to come to us with ideas.”

So the idea of the minister for higher education is that the private sector comes up with all the funding and all the planning for a new university. (Imagine the home secretary stating the goal of increasing the police force, but all the new police force would be paid for by the private sector, which, after all, has an interest in reducing street crime, and that it is not the intention of the home office to dictate how this private police force should operate.) This is exactly what an Italian minister would talk about at a press conference, only to be forgotten the following week.

The reaction from the academia, however, is different. In Italy, you would see people throw their hands in the air and say “madonna mia, in mano a chi siamo,” while the British are masters of understatement.

“We at Oxford feel that keeping the U.K. a world leader in science and research is a very important objective,” Ian Walmsley, Oxford’s chief research officer, “and we’re pleased that the government agrees with that.”

Stephen Caddick, for the University College at London says the proposal is “not uninteresting”.

Should the NYT and the ACM report facts?

Last week, the public editor of the New York Times wrote a post asking the following question: when the paper reports a statement from a public figure which is not true, should it also report the fact that the statement is false?

The post received hundreds of comments, mostly of the form “Wait, what? Is this even a question?” and it has stimulated a rich online discussion, mostly as incredulous that this would even be a question. In fact, the reluctance of mainstream media to report facts (as opposed to reporting statements) has been a long-standing problem. More than eleven years ago, Paul Krugman wrote “If a presidential candidate were to declare that the earth is flat, you would be sure to see a news analysis under the headline ”Shape of the Planet: Both Sides Have a Point.” After all, the earth isn’t perfectly spherical.

Krugman was joking, but something rather similar happened when reports of prisoner abuse surfaced during the wars in Afghanistan and Iraq. The Times was taken to task for never referring to the abuse as “torture” and eventually there was an article (from the public editor at the time? I wasn’t able to find it) explaining that since the Administration had taken the position that whatever happened to the prisoners was not torture, to say otherwise would have meant choosing sides in a political controversy.

If you are reading in theory you are probably aware of two bills making their way in the Senate and the House, called PIPA and SOPA, respectively, which have the goal of shutting down sites that illegally contain (or link to) copyrighted material. While the DCMA already allows the shutting down of web site in such cases, it can only be enforced within the US. PIPA and SOPA would allow copyright holders to go after a foreign website by requiring Domain Name Servers to stop resolving the domain name, and requiring search engines to stop linking to the website.

Objections to the bill include concerns about the unintended consequences of giving the state the power and the technical ability to “censor” websites, about the security vulnerabilities that would arise from any tampering with the DNS protocols, and the ramification, both in terms or quality of results and of free speech considerations, for search engines.

Meanwhile, the Research Works Act would forbid the NIH and other federal agencies to mandate open access publishing of the papers resulted from sponsored research. The intention of the bill, which is to restrict access to federally funded research, is an attack to the academic community, for which open access is an unqualified good thing.

As the leading association of technical and academic computer science professionals, one would expect the ACM to publicize the technical issues involved with SOPA and PIPA (the free speech issues are clearly a political issue on which the ACM might want to stay neutral) and to come out strongly in opposition of the Research Works Act, especially considering that ACM is a member of the Association of American Publishers, which has been the main lobbying force behind the bill, so that not speaking out is essentially the same as supporting the bill. The MIT press, for example, which is a member of the AAP, has come out against the Research Works Act.

The President of the ACM, however, has stated his intention of keeping the ACM away from any discussion of SOPA, PIPA and the Research Works ACT. (An ACM technical committee might produce a statement on SOPA and PIPA, but it would not be a position statement of the organization as a whole.)

Edited to add: the White House has come out against the DNS-blocking provision, and there are moves under way to amend both legislation to remove DNS-blocking. Meanwhile, as Doug Tyger correctly points out in the comments, the United States ACM Public Policy Council has sent letters to congress highlighting the technical concerns raised by the proposed legislation.