Congratulations

I was really delighted with all the prizes that were announced at STOC this year.

Our own Pasin Manurangsi received the Danny Lewin STOC Student Paper Award for his work on the hardness of the dense k-subgraph problem. This is the problem in which we are given a graph and a number k, and we want to find the set of k vertices that induces the most edges. Pasin, who is co-advised by Prasad Raghavendra and me, discovered a new, simple but ingenious reduction that establishes hardness up to almost polynomial factors.

I received the same award exactly twenty years ago, also for a hardness-of-approximation result established via a simple reduction. (Prasad also received it, nine years ago, for a hardness-of-approximation result established via a difficult reduction.) I then spent time at MIT, where Oded Goldreich was, and, partly thanks to his influence, I did my best work there. Pasin is spending this summer at Weizmann, where Oded Goldreich is, so, no pressure, but let’s see what happens. . .

Alistair Sinclair received the ACM SIGACT Distinguished Service prize, for his work setting up and leading the Simons Institute for the Theory of Computing.

Those who have been to the institute, that is, almost the whole theoretical computer science community, have seen that it is a place uniquely conducive to do good work. If you stop at think about what it is that makes it so, Alistair’s hand is behind it. The open layout of the second floor, with the whiteboards dividing the space and absorbing sound? Alistair worked closely with the architect, for a year, during the renovation, to make sure that the design would best fit the needs of our community. The friendly, competent and responsive staff? Alistair sat in all the interviews when the staff was recruited, and participates in their performance review. So many things happening and never a conflict? You know whom to thank.

More substantially, almost all the programs that we have had were, to some extent, solicited, and Alistair led the conversations and negotiations with all prospective organizers, shepherding promising concepts to approved programs.

Alistair has also been relentless in making people do things, and making them do things by prescribed deadlines, something that is notoriously difficult in our community. The Simons Institute programs have succeeded, in part, because of the tremendous amount of volunteer work that the organizers donated to our community, and while they would all have been extremely generous with their time in any case, Alistair made sure that they were extra generous. A personal anecdote: I was one of the organizers of one of the Fall 2013 inaugural programs. At that point, I was at Stanford and we were beginning to discuss the idea that I could come back to Berkeley. At some point, around October, I get a phone call from Alistair, and I assume he wants to talk about it. Instead, he goes “you know, I haven’t been seeing you much at the Institute so far. We expect organizers to be around a lot more.” A few months later, I got the offer to move to Berkeley, with a 50% affiliation at the Institute. Even knowing who my boss would be, I enthusiastically accepted.

Oded Goldreich received the Knuth Prize. I have already said how I feel about Oded, so there is no need to repeat myself, but I will add that I am also really happy for the Knuth Prize itself, that has managed to consistently make really good choices for the past 21 years, which is an outstanding record.

Finally, and I can’t believe that it took so long, the paper of Dwork, McSherry, Nissim and Smith, that introduced differential privacy, has been recognized with the Godel prize. I am very happy for them, especially for my matron of honor and former neighbor Cynthia.

Congratulations to all, and by all I don’t mean just the aforementioned awardees, but also our whole community, that nurtures so many great people, inspires so many good ideas, and makes being part of it such a joy (even when Alistair makes me do things).

Chariots of Fire: Silvio Micali on Oded Goldreich and Scientific Collaborations

At the aforementioned Oded Fest that took place at Weizmann a couple of weeks ago, Silvio Micali read from an epic prepared speech, which tied together the early work on foundations of cryptography, ancient Greece, the Renaissance, Viennese cafés, and the movies “Chariots of Fire” and “The Seven Samurai.”

Silvio has given his kind permission to share the speech, and he has put it in a pdf form that includes the pictures that he used as slides.

Here it is

Fests

I have been in Israel for the last couple of days attending an event in honor of Oded Goldreich‘s 60th birthday.

Oded has touched countless lives, with his boundless dedication to mentoring, executed with a unique mix of tough love and good humor. He embodies a purity of vision in the pursuit of the “right” definitions, the “right” conceptual point of view and the “right” proofs in the areas of theoretical computer science that he has transformed with his work and his influence.

A turning point in my own work in theoretical computer science came when I found this paper online in the Spring of 1995. I was a second-year graduate student in Rome, and I was interested in working on PCP-based hardness of approximation, but this seemed like an impossible goal for me. Following the publication of ALMSS, there had been an avalanche of work between 1992 and 1995, mostly in the form of extended abstracts that were impossible to understand without an awareness of a context that was, at that point, purely an oral tradition. The aforementioned paper, instead, was a 100+ page monster, that explained everything. Studying that paper gave me an entrance into the area.

Three years later, while i was a postdoc at MIT and Oded was there on sabbatical, he played a key role in the series of events that led me to prove that one can get extractors from pseudorandom generators, and it was him who explained to me that this was, in fact, what I had proved. (Initially, I thought my argument was just proving a much less consequential result.) For the most part, it was this result that got me a good job and that is paying my mortgage.

Like me, there are countless people who started to work in a certain area of theoretical computer science because of a course that Oded taught or a set of lecture notes that he wrote, and countless people whose work was made possible by Oded nudging, or usually shoving, them along the right path.

The last two days have felt a bit like going to a wedding, and not just because I saw friends that I do not get to see too often and because there was a lot to eat and to drink. A wedding is a celebration of the couple getting married, but it is also a public event in which friends and family, by affirming their bonds to the newlyweds, also affirm their bonds to each other.

I was deeply moved by the speeches given by Silvio and Shafi, and really everybody did a great job at telling Oded stories and bringing to life various aspects of his work and personality. But perhaps the most fittingly weird tribute was Benny Chor presenting the Chor-Goldreich paper (the one that introduced min-entropy as a measure of randomness for weak random sources, and the problem of 2-source extraction) using the original 1985 slides.

Speaking of public celebrations, there is less than a month left to register for STOC 2017, the “Theory Fest” that will take place in Montreal in June.

Turing Centennial Post 0: Oded Goldreich

[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

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

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

So this is what “FOCS” stands for

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.

CS276 Lecture 12: Goldreich-Levin

Scribed by Jonah Sherman

Summary

Today we prove the Goldreich-Levin theorem.

CS 276 Lecture 11: One-Way Functions

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 is hard, then there is a CCA-secure encryption scheme requiring a -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.)