It has been exactly one year since I moved to Italy.
Coming here a year ago, I expected that I would face some challenges and that there would be major life changes. Obviously, I did not know the half of it.
To put it mildly, 2020 is not shaping up to be a great year, so it is worthwhile to emphasize the good news, wherever we may find them.
Karlin, Klein, and Oveis Gharan have just posted a paper in which, at long last, they improve over the 1.5 approximation ratio for metric TSP which was achieved, in 1974, by Christofides. For a long time, it was suspected that the Held-Karp relaxation of metric TSP had an approximation ratio better than 1.5, but there was no viable approach to prove such a result. In 2011, two different approaches were developed to improve 1.5 in the case of shortest-path metrics on unweighted graphs: one by Oveis Gharan, Saberi and Singh and one by Momke and Svensson. The algorithm of Karlin, Klein and Oveis Gharan (which does not establish that the Held-Karp relaxation has an integrality gap better than 1.5) takes as a starting point ideas from the work of Oveis Gharan, Saberi and Singh.
Having spent some time in Japan, I have learnt of the tradition of holding a Bōnenkai, literally a party to forget the year. Held either as a company end-of-year party, or by groups of friends, it’s a get-together in which people drink a lot and forget the bad things that happened to them during the year.
It occurred to me that this is the complement of Thanksgiving, in which you get together to remember the good things that happened during the year.
I don’t think there is anything else left to say about the difference between Japanese and American culture.
Interestingly, there are a couple more possibilities. One could remember the bad things that happened during the year, as in the airing of grievances during Festivus.
Finally, one could forget the good things, which is very much the Italian attitude.
Edited to add: I don’t know how I forgot (ah!) but there is a famous Neapolitan folk song that goes
Chi ha avuto, ha avuto, ha avuto
Chi ha dato, ha dato, ha dato,
Scurdammuce ‘o passato,
simm’e Napule, paisa’
which is roughly
Who has received, has received
Who has given, has given,
Let’s forget the past
We are [all] from Naples
[In the provincial spirit of Italian newspapers, that often have headlines like “Typhoon in South-East Asia causes widespread destruction; what are the consequences for Italian exports?”, and of men who overhear discussions about women’s issue and say things like “yes, but men have issues too,” I am going to comment on how Babai’s announcement affects me and the kind of problems I work on.]
If someone had told me last week: “a quasi-polynomial time algorithm has been found for a major open problem for which only a slightly subexponential algorithm was known before,” I would have immediately thought Unique Games!
Before Babai’s announcement, Graph Isomorphism had certain interesting properties in common with problems such as Factoring, Discrete Log, and Approximate Closest Vector (for approximation ratios of the order of sqrt (n) or more): no polynomial time algorithm is known, non-trivial algorithms that are much faster than brute force are known, and NP-completeness is not possible because the problem belongs to either 
But there is an important difference: there are simple distributions of inputs on which Factoring, Discrete Log, and Closest Vector approximation are believed to be hard on average, and if one proposes an efficiently implementable algorithms for such problems, it can be immediately shown that it does not work. (Or, if it works, it’s already a breakthrough even without a rigorous analysis.)
In the case of Graph Isomorphism, however, it is easy to come up with simple algorithms for which it is very difficult to find counterexamples, and there are algorithms that are rigorously proved to work on certain distributions of random graphs. Now we know that there are in fact no hard instances at all, but, even before, if we believed that Graph Isomorphism was hard, we had to believe that the hard instances were rare and strange, rather than common.
It is also worth pointing out that, using Levin’s theory of average-case complexity, one can show that if any problem at all in NP is hard under any samplable distribution, then for every NP-complete problem we can find a samplable distribution under which the problem is hard. And, in “practice,” natural NP-complete problems do have simple distributions that seem to generate hard instances.
What about Small-set Expansion, Unique Games, and Unique-Games-Hard problems not known to be NP-hard, like 
I am sure that it is possible, under standard assumptions, to construct an artificial problem L in NP that is in average-case-P according to Levin’s definition but not in P. Such a problem would not be polynomial time solvable, but it would be easy to solve on average under any samplable distribution and, intuitively, it would be a problem that is hard even though hard instances are rare and strage.
But can a natural problem in NP exhibit this behavior? Now that Graph Isomorphism is not a plausible example any more, I am inclined to believe (until the next surprise) that no natural problem has this behavior, and my guess concerning the Unique Games conjectures is going to be that it is false (or “morally false” in the sense that a quasipolynomial time algorithm exists) until someone comes up with a distribution of Unique Games instances that are plausibly hard on average and that, in particular, exhibit integrality gaps for Lasserre relaxations (even just experimentally).
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.
[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
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.
[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.
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
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.
in theory 