On Paul Erdos and Kim Kardashian

This year is the centennial of Paul Erdős’s birth. Erdős lived most of his adult life as a traveling mathematician, “couchsurfing,” as we would say now, from place to place and from mathematical conference to mathematical conference. He wrote more than 1,500 papers with more than 500 different coauthors, introduced the probabilistic method and was the defining figure of the “Hungarian approach” to combinatorics. He died at age 83 while attending a mathematical conference.

Last year, we celebrated the centennial of Alan Turing’s birth. Turing and Erdős have become such iconic figures both for the impact of their work and for the fascinating facts of their lives. I would like to argue that the cultural archetype through which we interpret their lives is that of the saint. It is clearly that of the martyr saint in the case of Turing, while Erdős gave up material possessions and devoted his life to others, traveling everywhere and “preaching” to everybody, much in the mold of Saint Francis.

(A comparison of the Turing centennial celebration and Erdős’s, and a look at the frescoes of Medieval Catholic churches will show which kind of saint people are more interested in.)

The first step to become a saint of the Catholic church is to establish that the person exhibited “heroic virtues,” which is a great expression. This is an archetype that is not restricted to religion: you see it occurring in communist propaganda (Stakhanov, Lei Feng) and in every civil rights movement.

Saints were the “celebrities” of the Middle Ages, those whose life people liked to talk about. But contemporary celebrities come from a totally different archetype, that of the Greek God. Greek (and Roman) gods were petty and jealous, they cheated on their spouses, they were terrible parents, but there were good stories to be told about them. We don’t want (at least, I don’t) to live the life of a saint, but thinking about them is certainly inspirational and it makes us think that if someone can be so much better than us, maybe we can be a little better ourself in the practice of “virtues”, whatever this may mean to us. And we don’t admire gods, but, well, it’s probably fun to be one.

As usual, I have lost track of what I was trying to say, but I think that it speaks well of the academic community that we are more interested in saints than in gods, I will close by saying that my favorite saint of complexity theory is Avi Wigderson, I will keep to myself who my favorite god of complexity theory is, and I will leave it to the readers to contribute their picks.

Guest Post by Oded Goldreich III

[Oded Goldreich has written a new essay, on taste, subjectivity, and scientific evaluation, and he tells us a bit about it. -- L.T.]

This is my third guest posting on this blog, and I think it is time I express my gratitude to Luca for allowing me to benefit from the popularity of his blog.

I believe that the current posting is far less controversial than the previous ones, although it does express opinions. But these opinions refer to very general questions that address central aspects of scientific evaluation.

The first question refers to the apparent conflict between the desire to view scientific evaluation as objective and the realization that it is inevitably subjective (since it is based on opinions — expert opinions). I argue that the same holds with respect to understanding, and that the subjective basis of both understanding and evaluation does not contradict their claim to universality (to the extent that such a claim can be made at all). Thus, I believe that the concerns regarding subjectivity are overrated.

The second main claim is that imagination plays (and must play) a significant role in the evaluation process. The point is that evaluating the importance of a work requires evaluating both its past and future influence on the field. Clearly, evaluating the work’s future influence requires imagination (i.e., imagining the future development of the field). However, also evaluating past influence requires imagination, since one may need to imagine the state of the field without this work in order to realize which developments were influenced by it (and to what extent).

The third question refers to the role of personal taste in scientific evaluation. I claim that this role is grossly overrated, and that almost all that is attributed to taste is actually not a matter of taste (provided that one uses a reasonable definition of taste).

The essay, titled “On Scientific Evaluation and its relation to Understanding, Imagination, and Taste”, is available from my web-page.

Oded

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 www.wisdom.weizmann.ac.il/~oded/on-struggle.html

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

Threats

Faculty and students at UC Davis, and in a lot of other places, are outraged at the campus police who pepper-sprayed a group of students who were peacefully sitting down.

In their official response, the campus police said that the police officer in question felt “encircled and threatened” by the students, which reminds me of a classic South Park episode.

The context at UC Davis was that Chancellor Katehi had allowed “Occupy UC Davis” students to camp overnight on campus (which is ordinarily forbidden) for one night, but then sent them a message the following day that they were to disband, and she sent the police to enforce the decision. At Berkeley, Chancellor Birgeneau had similarly sent the police to disband an occupation, resulting in beat poets.

I can’t understand the rationale for these decisions. I don’t say “I don’t understand” as a passive-aggressive way of meaning “I disagree;” I genuinely don’t get what is going on. Chancellors are smart people, former professors, who are politically savvy and who care very much about students, or at least care very much about their relationship with the students. What could be so wrong with some students camping on campus that makes it, on balance, a rational decision to disband those camps with violence? Is it the Regents who are strongly against occupations? Is there a worry that an occupation would be unpopular with state officials, at a time when the California state budget has again a multi-billion shortfall that will require further budget cuts?

Edited to add: Another interesting question is why the police uses violence against peaceful protesters. After all, high-ranking police officials are themselves smart and politically savvy people, and such strategies are bad PR but also bad policing. Next time the campus police is called to diffuse a tense situation on campus, their presence will actually add to the tension. This interesting article by Alexis Madrigal (thanks to Sanjay Hukku for directing me to it) traces a change of police strategies to the 1999 WTO protests in Seattle.

Guest Post by Oded Goldreich

[Oded Goldreich has written an essay on the relative influence of "intellectual" versus "operational" goals in motivating our work, and on how this balance has changed in the past thirty years. In this guest post he tells us a bit about his methodology, his conclusions, and the changes he would like to see. -- L.T.]

The purpose of this post is to call your attention to my essay “On the status of intellectual values in TOC”, which is available from the web-page
www.wisdom.weizmann.ac.il/~oded/on-toc-val.html

Before providing a brief outline of this essay, let me clarify a few issues.
First, the term “values” is adopted from Sociology, where it is defined as the set of beliefs of a society (regarding what is correct, good, and/or desirable). By “intellectual values” I mean a specific type of values; that is, those that advocate curiosity, study, and understanding. In particular, I believe that the TOC community holds (and should hold) both intellectual values and instrumental values. The issue at hand is the balance between them. Second, I am talking about intellectual values, not about intellectual activities; that is, I’m talking about what exists in the background. Third, I am talking about the TOC community as a social group, not about individuals who are members in that group; that is, I’m talking about the sociology of TOC. And last, my intention is to call for corrective actions, not to complain on the current state of affairs.

In the essay I study the status of intellectual values in the TOC community during the last three decades. Specifically, analyzing the motivational parts of papers that appeared in several STOC proceedings, I found evidence to my feeling that the importance attributed to intellectual values has declined in the last decade (or so). The said evidence is conditioned on a number of assumptions, which are spelled out in the essay.

I then discuss three theories that may be used to explain the decline of intellectual values in TOC (or rather three phenomena that may cause this decline). This discussion may be of interest also to readers that are unconvinced by my thesis and/or my empirical study, because it indicates potential dangers that loom over TOC.

The most intrinsically oriented theory asserts that intellectual values play a bigger role in the early stages of the development of a field, a stage which is marked by many works of explorative nature. In the essay I explain why I do not believe in this theory in general, and point out that it fails to explain the specific data that I gathered. Instead, I suggest to seek the causes elsewhere, specifically, in sociology. Two sociological theories seem most applicable here:
The first refers to the dynamics of the field (i.e., TOC) itself, while the second refers to the effect of society at large.

The first sociological theory asserts that as a field become more successful
(or, actually, is considered so from the outside), the competition within the field intensifies, and this creates pressures towards “objective” measures of accomplishment that can be reviewed from the outside. Such measures are typically oblivious of intellectual contents. Thus, under the reign of (externally monitored) competition, intellectual values decline.

The second sociological theory refers to the effect of the Zeitgeist on any activity that takes place in society (including scientific research). Specifically, the claim here is that intellectual values are in decline in the Western society for more than one hundred years, and that the decline has become more and more drastic with time.

Although my real objective is to advocate a restoration of the intellectual values in TOC, I believe it is helpful to study the past as well as the forces that might have affected it and may affect the future. In particular, the claim that things were different in the past provides some evidence that they may be reversed in the future. I admit that opposing the social forces that cause the decline of intellectual values is far from being easy. But I think that such an opposition is possible, especially since the TOC community is relatively small (which facilitates the creation of solidarity and the effecting of change). If the TOC community is determined to change its culture, then no outsider can prevent this. The outsiders will have to adapt to what the TOC community values; they have no choice (i.e., there is no alternative TOC community). It is only up to us!

In order to avoid claims of being too lofty, I provide a few concrete suggestions for the defense and promotion of intellectual values in TOC. These suggestions refer to actions that individuals can take, but they will be effective only if these individual actions will become sufficiently common.

• Let the intellectual values guide you in your own research and in your interaction with other researchers.
• When presenting a scientific work, provide an explicit account of the (current) motivation for this work.
• When serving on either a PC or a hiring/promotion committee, try to steer the committee towards taking decisions on the basis of a real understanding of the contents of the work being considered rather than on the basis of some superficial “objective-looking” measures.
• Object to the dominance of vulgar competition wherever it emerges.

Indeed, individual actions may be much more effective if they are socially coordinated. Thus, it may be useful to make these actions a topic of social discussion, to form groups that are committed to promote them, to create forums that promote them, etc.

A final note: Due mainly to technical reasons, I expect not to be able to participate in possible discussion that may evolve in this blog. Thus, if you wish to communicate with me regarding these issues, please write me directly (via email). (I will not object if you later post our correspondance.)

Oded Goldreich

Beauty and the computer

This week the New Yorker has a profile of Magnus Carlsen, a young Norwegian chess player that is currently the #2 ranked player in the world (he has been #1 in the past).

The article discusses how the game has been changed by the availability of computer programs that are now unbeatable even by the top players, and the fact that the younger generation of players (but not Carlsen) grew up playing against computer programs. The following quote was interesting:

Computers have no skills and they have nothing approaching intuition. Carlsen finds their games inelegant, and complains about “weird computer moves I can’t understand,” whereas in talking about his own game he speaks of achieving “harmony” among the pieces on the chessboard, and even of “poetry.”

It struck me that we could see in our lifetime computer programs becoming better than human mathematicians in raw technical skills, and that the above quote could reflect our future attitude toward proofs found by computers. “Where is the statement of this lemma coming from?”, “this argument has no elegance!”, and so on.

Two interesting questions

I would like to comment on two questions I have read on the theoretical computer science Q&A site.

Boris Bukh asks a rather novel question about the complexity of Max 3SAT. Given a 3CNF formula , we know it is NP-hard to approximate the maximum number of clauses that can be simultaneously satisfied. But how many bits of information can we efficiently compute about Put another way, how many possible values of can we efficiently rule out? If the formula has clauses, then we know that the possible value of is one of possible values, but it is difficult to see how this can be narrowed down much more. On the other hand, there is an argument that you cannot narrow the set of possible values down to a constant, or even a constant times , unless the polynomial hierarchy collapses. But there is still a big gap.

John Sidles asks a series of questions that are nominally related to but that can also be phrased about the proof that, say, every problem in has a uniform family of polynomial size circuits.

In the latter setting, we start by showing that from a Turing machine , a time bound , and a size bound , we can construct a circuit of size polynomial in , , and the size of , such that on every input of length the circuit simulates what the Turing machine does on input for steps. If a language is in , then there is a Turing machine and a polynomial bound such that decides on every input of length in time at most ; given , we can then construct a circuit that solves on inputs of length by applying the circuit simulation with .

But, the question is, what if we do not know ? This might sound like a rather strange issue, like someone objecting to the commutative property of addition by saying, how I am going to use if I do not know and ?

Cryptography at STOC/FOCS

It has been too long and now there is no point telling stories from the last two days of FOCS, such as the distinguished theoretician who “flew” on the zip-line on Fremont street and then got drunk at Double Down and asked the two big scary guys who were playing pool if they were twins (they said they were).

As soon as the videos of the conference go online, however, I would suggest to everybody who wasn’t there to watch Dan Spielman’s invited talk, which was phenomenal. Dan talked about the problem of solving linear equations when the constraint matrix is the Laplacian of a graph, the result of a long-term collaboration with Shang-hua Teng. Two major parts of this research program have gone on to become their own research area:

You Read it Here First

Last year, I wrote on the losing tactic of promoting oneself by disparaging the competitors, using a parable attributed to Silvio Micali.

This week a Dilbert cartoon covers the same ground.

Binary Search Proves Existence of God

No that’s unfair, but this post sort of argues that efficient algorithms disprove the non-existence of God.

Anyways, it’s an actually good introduction to concepts in theoretical computer science appearing in one of the most widely read political blogs.