TOC: a Personal Perspective (2021)

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?

17 Comments on TOC: a Personal Perspective (2021)

  1. I agree with much that Omer has said, and most of all with his analysis that asserts that the source of all trouble is an extreme and weird lack of self-respect. It is not that we should do better on that angle. Even a modest/minimal level of self-respect is nowhere to be found. In my view, this is also the sources of all ills I have been voicing wrt FOCS/STOC (see, e.g., http://www.wisdom.weizmann.ac.il/~oded/on-stocfocs.html), but these are minor issues compared to the stunning lack of self-respect.

    Like

  2. Oded Goldreich // April 15, 2021 at 8:31 am // Reply

    Opss… Pushed a wrong key. I wanted to add that I disagree with Omer on something he said at the beginning, where he lament on the lack of agreed-upon challenges. This is not important at all. If at all, what matters is agreement on achievements. However, what is really important is a deep internalization of the fundamental nature of the contents of our field (not merely a lips-service or a nod).
    I find it amazing that experts in the field fail to see it. This field is the most fundamental one, since it deals with the nature of efficient computation whereas all of modern science is based on the “mechanistic” worldview (i.e., viewing the world as an automatic machine/mechanism that evolves based on simple rules). Taking this view, nothing is more fundamental than understanding the limitations that any process evolving under such rules may have.

    Like

    • Thanks Oded, this was not my view but roughly quoting others, which I disagree with. I revised the post to reflect that this is not mine (added quotations, even that those are not exact quotes).

      Like

  3. normanstresskopf // April 15, 2021 at 8:19 pm // Reply

    Maybe the success of TOC had in the past been fueled by a coincidence of circumstances:
    a) Digital computers as emerging new technology motivating/justifying such investigations, which required little background (beyond straight thinking) in order to make first contributions that could furthermore easily (and privately) be evaluated by “running code” as immediate feedback.
    b) Strong connections to Combinatorics (cmp. Karp’72) as a part of Mathematics which had been quelled for a century and therefore was “hungry” and excited contributions from many secretly discrete Mathematicians.
    c) Similarly for the many (pure) Logicians that had been raised in the era of Goedel and Tarski (“reduction”), and now finally found a new field to contribute to (cmp. Cook’71 with quantitative “reduction”).

    Liked by 1 person

  4. Couldn’t agree more: “If TOC is in a continuous crisis, it is the most wonderful crisis possible.” We all agree on one point, and that we love doing theory regardless. At the end of the day, the disagreements are all on the lower order bits.

    Like

  5. Omer your take sounds optimistic alas, the current trouble with TCS- which at its core strives to understand something as profound as power of computation is that it has evolved to reward the people who play the averages and work on the next most easily accessible low effort problem that a few other people who also work on the next most accessible low effort problem find interesting. This creates an unhealthy feedback loop which is actively suffocating for people who are truly courageous to explore the profound at their own cost of time and effort. When the *real* challenges are hard the academic survivalists make their own *unimportant* problems, may be solve them and pat each other on the back and then rinse and repeat 😦 How Sad ?
    This is really why in my opinion real *action* and *progress* is hard to find in comparison to earlier decades of beautiful work. That “We do not have agreed-upon challenges” as quoted in your post is a visible conjoint feature of this slowly degenerating state of affairs.

    Also self-respect is an individual trait that stems from having done something worthwhile, [omer Reingold removed personal comment here which could be misinterpreted] But perhaps self respect is too much to expect of someone playing the game of averages not driven by curiousity of the profound.

    Except for a handful of people all you find are those working on something else far from the essence, passing of as doing TCS. Pardon me for what sounds like cynicism but the change will come from outside the field at least if the current trend continues- of course this is modulo those handful of courageous inspiring people.

    Like

    • Please forgive me for removing a sentence in your comment. I’d like to make sure that the discussion doesn’t become personal.

      As for the content of your comment I disagree and repeat that the this criticism in various versions have been uttered for decades and I believe that history proved it wrong.

      Like

  6. Could anybody point to the social media discussions Omer Reingold alluded to?

    Like

  7. > Feel free to claim ownership in comments .

    I initiated such a thread on my Facebook timeline a little over 2 months ago which generated many more comments than I was expecting, so maybe that is the post you’re referring to but I’m not sure. In any case, whether or not it was my post, this topic is something I’ve been thinking about for some time now.

    I’m a big fan of TCS of course, else I would not be doing it. I agree that we have made major contributions to core computer science and beyond, both philosophically (ZKP’s, the power of randomness, quantum computing, etc.) and in industry (I still remember watching a YouTube video a couple years ago in awe as Apple CEO Tim Cook uttered the words “differential privacy”, and now we see multiple industry patents proposing to use DP for real applications, like as part of a solution to train autocomplete for texting on smartphones without the phone vendor learning the content of our text conversations). I also agree with Avi’s opinion in his talk that the value of TCS should not be measured in terms of adoption of our results into industry. Those are important and should count, but our philosophical contributions that help humanity understand the nature of computation also hold great intellectual value.

    My frustration, and it seems the frustration of some others based on comments on my post and other conversations, is not regarding the relevance or irrelevance of TCS. I believe what we do is relevant, and important. So why did I say “TCS is lost” at some point in my post? In PC chats, conference talks, and informal discussions, too many times have I witnessed admiration for techniques and pretty math over motivation. It is as if our community at times forgets that we are framing and solving important problems and not simply working on cool math puzzles for their own sake. My post and the comments combined are all quite long, but I’ll paste some excerpts here (I’ll only post things I myself wrote). The original post was viewable only by my Facebook friends, and some may have commented not expecting for their comments to be viewable by the whole world, so it’s probably best that I do not make the original post public and won’t link to it here.

    — Excerpt 1: “TCS paper introductions which make up nonsensical reasons for why the work is important are the norm, so our community has unfortunately been trained to mostly ignore motivation. The decision of what is and isn’t important*** is then arbitrary: just as precious gems have value by mere convention, work on X should appear in our top venues because work on X has appeared in our top venues in the past, where the first paper in the series managed to be accepted by chance, or perhaps because it had ‘new techniques’.
    Which leads me to: the development of new techniques is of course important, but it is of secondary importance. Developing new techniques is a consolation prize for failing to solve an important problem, with the hope that these new techniques may one day prove useful for a resolving a problem that’s actually important. But if the community has no confidence in what’s important, then what should have been the consolation prize becomes the main prize, and researchers are incentivized not to identify and solve important problems (because who knows what’s important anyways?), but to write ‘Rube Goldberg’-type proofs that give the illusion of mystery and magic, to intimidate program committees into prostration before your mathematical godliness.” ***”important” here should probably have been “perceived as important” (also, context: this is mostly relevant in conference refereeing)

    — Excerpt 2: “Historically, we had non-universal computing machines 100 years before Turing, via Babbage. When Turing and others came along and proposed universal models of computation, the motivation was very much coming from practice and improving upon actual calculating machines people were building. Once Turing put forth his mathematical model (the Turing machine), he went and actually built a real physical computer based on his model (or perhaps collaborated with engineers who built it :)) and used it to help the Allied Forces in WWII by cracking the Enigma machine. John von Neumann was a mathematician who contributed to computer architecture. Not going as far back, I’m sure other TCS pioneers like Dijkstra and Knuth would proudly label themselves as ‘programmers’, and that their motivation in developing TCS was to understand programs that are intended to be written and actually used. I agree with XXX that at some point puzzle solvers noticed we had a lot of fun problems to work on, so they came into the field to contribute. I think that it’s a good thing to have clever problem-solvers jump into the field to help solve our hard problems, but we shouldn’t then get confused about our identity and forget that the reason our field came into existence was not to solve puzzles, but rather to solve important problems.
    … the resolution of certain questions in complexity theory (in either direction) may or may not have any practical importance. For example, what if one day someone shows that TSP is in DTIME(n^{100}) but not DTIME(n^{99})? But P vs NP, P vs BPP, RL vs L, BQP vs P, etc. are all fundamental philosophical questions about the nature of computation itself. It turns out they are hard to resolve, but they’re not interesting because they’re hard — they’re interesting because they’re fundamental. I would say the time hierarchy theorem is also fundamental and important, despite not being hard to prove, and likewise for the undecidability of the halting problem.”

    — At some point in a comment I quoted an old blog post https://infoweekly.blogspot.com/2010/09/problem-solving-versus-new-techniques.html, which I strongly agree with.

    Like

    • Thank you Jelani for sharing some of the discussion here! I will let most of your comments stand as I already discussed my point of view in the post. Let me say a few things:

      1. This criticism (and stronger criticism) is not new. I remember an important figure in our community comparing, during my PhD (!), much of our efforts in complexity theory to primitive people that are trying to get closer to the moon by climbing a tree or a mountain (rather than developing the physics and engineering that finally got humans to the moon). And still all the things that excite you about TCS’ impact keep on happening.

      2. Developing techniques is extremely important rather than a consolation prize. I know of many papers that lead to great progress on new results and would probably not have been published unless there was an excuse beyond the new techniques. In fact, as I tried to point out, there is room for many sorts of papers and all of those papers are responsible to the success of TCS.

      3. There is a lot of room for improvement. I have my own ideas. But TCS is not lost, it is very much alive. I know that your way of stating your criticism is kind of a shock therapy but I urge you and all others at your level of leadership to weigh their words and their impact on more junior people. You have the tools and responsibility to bring on change.

      Liked by 1 person

  8. > I know that your way of stating your criticism is kind of a shock therapy but I urge you and all others at your level of leadership to weigh their words and their impact on more junior people.

    You are probably right on that. An undergraduate we admitted to our PhD program this cycle (virtually) met with me and asked what I thought about the future of TCS, right after he referenced my post. I was a bit surprised he even knew about the post since it was private, but I should have known better that even private posts online may spread farther than one would think! I assured him that I do think TCS is still making important contributions and gave several examples. By the way, I fondly remember one of my earliest exposures to our field. I was an undergrad and it was Fall 2004, and I was taking “Introduction to the Theory of Computation” with Mike Sipser. At some point in the semester Mike printed out what must have been 100+ copies of a brand new ECCC upload (https://eccc.weizmann.ac.il/report/2004/094/) and very excitedly handed them out to every student in the course. Thank you for that memory!

    Liked by 2 people

  9. Mahdi Cheraghchi // April 22, 2021 at 9:03 am // Reply

    I think one contributor to CS theory’s identity challenges that is less talked about is the fact that many (most?) theorists in academia, especially in the US, are based in a College of Engineering within their institutions. That can dramatically set the expectations on what they should be doing and where their research trajectory has to go along a path that is possibly completely against their ideals, as well as the interests of the CS community. To me, there is a strong case to be made to locate theorists in Colleges of Computing or Sciences, or math departments (while the latter can bring challenges of its own, and the fact of having no “perfect home” can be a significant cause of the identity dilemma).

    Like

  10. Mahdi Cheraghchi // April 22, 2021 at 12:00 pm // Reply

    By the way, there seems to be a typo, unless “Avi Wenderson” is a theorist I was totally unaware of 🙂

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: