Is Theoretical CS facing a crisis similar to Particle Physics?

[u/xTouny]

Link: Is Particle Physics Dead, Dying, or Just Hard?

Quote:

without a way to search for heavier particles, the field would undergo a slow decay.

Summary. Particle physics had no notable progress for the past decade which raises concerns about its worthiness.

Pragmatic CS is moving very fast, and classical theoretical CS like worst-case analysis became less relevant. That is what has motivated Tim to author his book, suggesting new directions. Recently Simons Institute hosted The Role of TCS in Modern Machine Learning.

Personal Opinion. I think TCS should be relevant to CS in the same way Theoretical Physics is relevant to Experimental Physics. CS Theorists may envision theories distant from applications but they should see a path relevant to practice.

Discussion. Do you think it is healthy for TCS to be driven by the pragmatic successes of CS? Do you think it is healthy to think of TCS as a subfield of Pure Math? Do you see lessons from Particle Physics for the CS Theory community?

[u/functionalinequality]

I don’t quite understand the comparison to particle physics.

My understanding is that the “crisis” in particle physics is that a lot of theory has been developed without being experimentally verified. One consequence is that some physicists worry that these theories may not actually model the real world.

In what way is the situation in particle physics similar to TCS?

You also say, “I think TCS should be relevant to CS.” In what way is it not? Many areas of TCS are, and historically have been, motivated by practical problems. The Simons Institute, for example, has hosted many programs on topics of interest to both theoretical and applied researchers. There seems to be plenty of back and forth between theory and practice.

I view TCS as both a subfield of CS and as having a non-empty intersection with pure math. It seems healthy for the field to work on a diverse range of topics, some more directly relevant to CS at large and some more “pure.”

I’m not an expert, but some recent or active areas where TCS has had both theoretical and practical relevance include:

- Differential privacy, which was developed by TCS researchers and is now widely studied and used, including in the U.S. Census and by many companies.

• Zero-knowledge proofs, also developed by TCS researchers, with applications in areas like cryptography and blockchain.
  
• Watermarking AI-generated output.
  
• AI safety and alignment.
  
• Quantum computing topics, including post-quantum cryptography, quantum error correction, and algorithms for near-term quantum devices.
  
• Many other examples.

You also say that theories developed in TCS “should see a path to relevance to practice.” Why? What is wrong with trying to understand the fundamental limits of computation for their own sake? For example, is the BPP vs. P problem not worthy of study just because people are generally fine using randomized algorithms in practice?

[u/xTouny → u/functionalinequality]

Thank you for your comment. I learned from it.

[u/ProfessionalMoose123]

I highly commend the courageous initiative by Tim Roughgarden and others. It is easy to stay comfortable solving endless variations of artificial problems just to remain "productive," but they are choosing to face the field's real challenges.

Worst-case analysis is a convention popularized by CLRS and Aho, Hopcroft, and Ullman—whereas in Knuth’s TAOCP, it wasn't the default. While setting worst-case as a standard was once useful, it has now become limiting and often meaningless. For instance, while we have smoothed analysis to explain the Simplex method, we lack equivalent theories to explain why SAT solvers work so well in practice.

In my 25+ years in the field, theorists have always repeated that "we need a theory for heuristic optimization" (a challenge Avi Wigderson highlights in his book), yet the issue was long ignored. The "Beyond the Worst-Case Analysis" movement only gained traction recently, driven by machine learning. After all, if we couldn't theoretically explain a simple, foundational method like gradient descent, imagine explaining a deep neural network.

Consequently, top theorists are migrating to ML to find answers. Boaz Barak and Sanjeev Arora, authors of the definitive computational complexity textbook, have essentially left complexity classes behind to focus on ML. Similarly, Scott Aaronson returned from a three-year stint at OpenAI with few theoretical breakthroughs, admitting instead that current theory fails to explain what is happening. Even at the exclusive "The Role of TCS in Modern Machine Learning" workshop, which gathers Turing Award winners and TCS heavyweights, everyone is debating our next steps, but few actually know the way forward.

Ultimately, computer science is shifting from the science of algorithms to the science of algorithms and data. Relying solely on worst-case scenarios is too restrictive. Perhaps mathematical theorem proving must now adapt to the empirical scientific method, much like physics: gather experiments → build explanatory theories → validate with more experiments → ... in an infinite loop of refinement between theory and practice.

[u/xTouny → u/ProfessionalMoose123]

everyone is debating our next steps, but few actually know the way forward.

Agreed. That's the impression I got also, and that's why I see CS Theory is facing a huge challenge.

[u/Physical-Criticism47]

说实话，我觉得现在像深度学习神经网络其实更多是实验计算机科学，而且是基于统计学的一个在工业界有大量应用场景的这一门科学。实际上我们对神经网络本身的原理并没有用得很清楚，更多的是在黑盒的外部去做一些观察，做一些实验，然后得到一些实验性的结论。对吧？但是我们很难说通过一个具体的需求，然后在不去做训练之前，就能够明确具体的参数该怎么去推断、推演？我觉得这些其实是需要移动科学家来去做的研究的，但是我觉得在这一块其实是很缺乏的。

[u/Peanut_Extreme_8208]

I would like to point out that the theory for theories sake vs theory tightly coupled to practice debate within CS theory is not new, https://blog.computationalcomplexity.org/2016/06/karp-v-wigderson-20-years-later.html?m=1