You are currently browsing the tag archive for the ‘Oded Goldreich’ tag.

[I solicited essays from gay and lesbian colleagues on the occasion of the Turing centennial, and I was (pleasantly) surprised when Oded Goldreich offered a contribution too. Oded's essay is not very specific to the academic or computer science community, and he talks about topics that are probably "obvious" to gays and lesbians. On the other hand, maybe they are not so obvious to some readers, and so Oded's piece might be a good "introduction" to the posts that will comes later. On this note, you may also want to read this week's unusually good modern love piece. -- L.T]

I decided to contribute to this discussion of gays and lesbians (or rather LGBT) in academia (or rather in TCS/TOC) nowadays, because I think it will be wrong if only gay and lesbian colleagues will write about it. While I agree that this topic has more immediate implication on their life, it is a central social issue and as such it affects the life of each human and each human should be interested in it. The latter claim can be phrased in several ways including “nothing that is human is alien to me” and “no one is free while others are oppressed.”

I wish to address three related aspects of the topic, which I’ll call the “practical/life” aspect, the “cultural” aspect, and the “political” aspect. I consider all that I am about to say quite obvious and well-known (at least in some circles), but still believe that obvious things ought to be stated too.

THE PRACTICAL/LIFE ASPECT.

In a society that subscribes to ideologies that range between individualism to liberalism and humanism, a person’s sexual orientation should not be a social issue. But, of course, we know that this is and has been an issue in such societies, which demonstrates that these societies were and are far from what they pretend to be. In particular, severe forms of explicit oppression were a significant part of the life realities of LGBTs for several centuries, and softer forms of implicit oppression are still effecting the life of LGBT nowadays.

While it is true that attitudes towards LGBT have improved significantly in some societies and in some social groups, it is important to remember that (1) they improved less in other societies, (2) softer forms of oppression are still existing even in more progressive societies, and (3) the shadow of past centuries of oppression is not easy to brush off overnight.

THE CULTURAL ASPECT.

Historically, LGBT gave rise to a sub-culture (or a counter-culture), which has been very inspiring and carried a great emancipatory potential (in addition to being great fun and full of beauty). Let me use the term “queer culture” and align myself with it; that is, I view myself as queer. Let me also clarify that LGBT people are not necessarily queer nor should they be required to be queer. Still, I think I am allowed to advocate the queer culture.

The queer culture has great emancipatory potential because it is rooted in central aspects of its members lives and it couples these personal aspects with a rejection of some “dead” and dysfunctional aspects of the mainstream culture (e.g., the domination of instrumental rationalism (*) and the total division between life, beauty, and ideas). In other words, I am talking about a combination of a form (or culture) of life and a revolt against the existing order (and in particular its oppressive aspects). Indeed, this combination is a bridge between the personal and the political.

(*) By “instrumental rationality” I refer to confining rationality to low-level calculations of ends, while forgetting that a deeper sense of rationality calls for a critical reflection of the ends and purposes (rather than the non-critical and absent-minded conforming and adoptation of ends suggested by others). This is not unrelated to accepting a total division between real life on one hand, and ideas and beauty on the other hand, which makes life poor and the ideas and beauty deteched.

THE POLITICAL ASPECT.

The politics of LGBT face two possibilities. The first possibility is to join a coalition of oppressed people, which must include also the economically oppressed, and contribute to a deep social change in society. This is not an easy choice, because homophobic attitudes tend
to strive among the oppressed (since the dominant social groups promotes oppression, hatred, and fear among the oppressed themselves).

The second possibility is to focus on promoting its own interests, and remain neutral with respect to other forms of oppression. This is the easy choice, since the dominant social groups encourage the creation of various special interest groups that attempt to promote specific issues while not challenging the basic structures of society.

THE TOC/TCS ASPECT.

This brings us back to the life aspect, and my impression is that the TOC/TCS community is relatively LGBT-friendly. One may say that not being identified as gay, I would not have experienced negative reactions, but on the other hand it allows me to monitor what “straight” people say of gays. Recall that some LGBT are “out” in the TOC, and yet I never heard anything negative being said about this.

Oded Goldreich

[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

[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

[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

At the STOC 2009 business meeting, Silvio Micali announced a new conference, Innovations in Computer Science (ICS), whose first edition will be in Beijing in January, 2010.

This is a conference that aims to be the venue for the first papers in new areas. This prompted people to ask me afterward if we shouldn’t start a new conference devoted to second papers. I thought this was an appealing ideas, and perhaps the conference could be called Follows-up in Computer Science; a snarky colleague, however, suggested that we already have two such conferences and they are called STOC and FOCS.

ICS has a steering committee entirely composed of past and future Turing Award winners, so surely they know what they are doing. A common complaint I heard, however, was that it isn’t clear exactly what the motivations and the goals of this conference are, what papers are being sought (surely you cannot fill up a 30-paper conference with first papers, each opening up a new area), and so on.

Helpfully, Oded Goldreich, one of the promoters of ICS, has written a statement about the goals ICS, as well as a longer essay on What is wrong with STOC and FOCS. The arguments made in the essay are Oded’s motivations for the new conference.

As I have said before, I agree with the importance of conceptual innovations, and of simplicity, but I disagree with the claim that our current review system undervalues such points. Hence, I think that initiatives such as the “letter on conceptual contributions” and now ICS will not correct an imbalance, but rather will create an imbalance, penalizing the necessary, hard, and unglamorous technical work by which we understand new ideas, exploit and simplify their applications, and create the conditions such that the next new ideas are “in the air” and the right person at the right time can get them, and so on.

Scribed by Jonah Sherman

Summary

Today we prove the Goldreich-Levin theorem.

Summary

Today we begin a tour of the theory of one-way functions and pseudorandomness.

The highlight of the theory is a proof that if one-way functions exist (with good asymptotic security) then pseudorandom permutations exist (with good asymptotic security). We have seen that pseudorandom permutations suffice to do encryption and authentication with extravagantly high levels of security (respectively, CCA security and existential unforgeability under chosen message attack), and it is easy to see that if one-way functions do not exist, then every encryption and authentication scheme suffers from a total break.

Thus the conclusion is a strong “dichotomy” result, saying that either cryptography is fundamentally impossible, or extravagantly high security is possible.

Unfortunately the proof of this result involves a rather inefficient reduction, so the concrete parameters for which the dichotomy holds are rather unrealistic. (One would probably end up with a system requiring gigabyte-long keys and days of processing time for each encryption, with the guarantee that if it is not CCA secure then every 128-bit key scheme suffers a total break.) Nonetheless it is one of the great unifying achievements of the asymptotic theory, and it remains possible that a more effective proof will be found.

In this lecture and the next few ones we shall prove the weaker statement that if one-way permutations exist then pseudorandom permutations exist. This will be done in a series of four steps each involving reasonable concrete bounds. A number of combinatorial and number-theoretic problems which are believed to be intractable give us highly plausible candidate one-way permutations. Overall, we can show that if any of those well-defined and well-understood problems are hard, then we can get secure encryption and authentication with schemes that are slow but not entirely impractical. If, for example, solving discrete log with a modulus of the order of ${2^{1,000}}$ is hard, then there is a CCA-secure encryption scheme requiring a ${4,000}$-bit key and fast enough to carry email, instant messages and probably voice communication. (Though probably too slow to encrypt disk access or video playback.)

Summary

Today we show how to construct a pseudorandom function from a pseudorandom generator. Read the rest of this entry »

Summary

Today we complete the proof that it is possible to construct a pseudorandom generator from a one-way permutation Read the rest of this entry »

Oded Goldreich has started a site in which he is going to collect selected recent papers in theoretical computer science.

He introduces this project with very interesting reflections on the matter of scientific exchange and communication:

My impression is that FOCS and STOC do not function any more as forums devoted to the presentation and exchange of ideas (but rather function as “weight-lifting competitions”). The question is what can be done to serve the need for the lost forums. One answer is provided by various personal blogs in which various researchers present their own choices of (relatively) recent works that have drawn their attention.

My problem with many of these blogs is that they cover the obvious (i.e., they all focus more or less on the same “hot results” that draw everybody’s attention). I would like to contribute to the project of regaining forums devoted to the presentation of ideas in a different way; specifically, by calling attention to works that have fascinated me although they were not necessarily labeled as “hot”.