Editorial note: this post has been written in celebration of 25 years for “TOC: a Scientific Perspective (1996),” by Oded Goldreich and Avi Wigderson. In the process, I have been made aware of a Facebook discussion from a few weeks ago (which I don’t know how to link to), and to Avi Wenderson’s recent talk that addresses this discussion (and more). I will not attribute statements from the Facebook discussion to individuals (nor will I specify its initiator), as they may not identify with the statements, when taken out of their original context or in the editorialized version here. In any case, this specific discussion is not the point. Feel free to claim ownership in comments .

———————————–

I’m sure that, like me, you read on social media: “TOC is in crisis, scratch that, it is lost! We do not have agreed-upon challenges (that are not way out of reach) and do not know how to evaluate papers. Therefore our conferences are favoring progress in techniques and favor complicated papers on obscure problems over progress on important problems (in fact, there is shortage of interesting work on relevant problems). Our flagship conferences are broken and newer conferences, that aimed to do better, have become just more of the same. This is not TCS as we remember it!”

There are many points with which I agree. Like others, I have been critical at times about the way we do some things, mourning papers and subfields that our conferences have missed. On several occasions, I have been pushing for change. At times I was successful but in other instances my suggestions were deemed radical by the powers that be (and more modest/timid suggestions were adopted). But did TOC really lose its way?  

One of the commenter was saying “I have been hearing these complaints about focs and Stoc for more than ten years. They have come from powerful people that sit on committees. … So why nothing changes?“ This comment strikes a chord with me, but let me revise it and say that I have been hearing such complaints for the last 25 years (since attending my first conference), and it is almost always stated by the powerful people, those that have the responsibility to shape the field.

Following the continuous self-criticism, we are likely to assume that TOC is a dysfunctional field and has been so for many years. But if we look at the research achievements of TOC in the last quarter century, we must conclude that this was a glorious period. And the contributions of TCS were on different fronts. Contributions to applied CS and industry, growing contributions outside of CS as well as progress on fundamental questions within TOC. Said progress was obtained by simple papers and by complex and long papers. By papers developing new techniques, by papers making progress on known problems and by papers that introduced new problems, models or even papers that initiated new subfields. They have been made by breakthrough papers and by long sequences of modest papers. By papers in FOCS/STOC and papers in other conferences. So if TOC is in a continuous crisis, it is the most wonderful crisis possible.

During my studies (ages ago), I was intensely attracted to TOC. But at the same time, I felt that the field is under constant external attack. It was claimed that we are not as deep as Math and not as useful as CS. Many fewer universities than today have been hiring theoreticians. The field was grossly underfunded (still underfunded but less grossly) but still calls have been made to reduce funding to any area in which TOC is not directly serving other, more applied areas. The dissonance between my intuitive attraction and external criticism could have deterred me from TOC, but there were incredible leaders of TOC that effectively defended the field and shouted – look, something amazing is happening here. “TOC: a Scientific Perspective (1996),” by Oded Goldreich and Avi Wigderson gave me courage to continue. 25 years later, the case they once made in defense of TOC is so much easier to support (and they kept on making this case throughout the years in essays and books). As Avi argued, TOC’s success have brought growth and diversification, influx of young talent, scientific respect, industrial respect, and societal respect. We should do better on self-respect.

I am of course not advocating resting on our laurels’. Like in Alice’s adventures, in our fast field, it takes all the running we can do, to keep in the same place. If we want to get somewhere else, we must run at least twice as fast as that! Constructive criticism is a good thing but our tendency for alarmist/defeatist cries is not serving us well. As someone who grew (scientifically) in an atmosphere of struggle, I am grateful for the progress made in establishing our field by the generations that preceded me. We shouldn’t take for granted how easy we have it. But more importantly, confidence in our field and optimism towards our future are important for our impact on the world (I discussed one aspect of this here). Finally, thinking of students interested in TOC today and hearing the most powerful people in the field announcing that it is lost. I ask myself, who are the Avi and Oded that will give them the needed courage and optimism? The answer is still that their Avi and Oded are the very same Avi and Oded from my student years. But isn’t it about time that we lend a hand?