Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020

Shuchi Chawla, Jelani Nelson, Chris Umans, David P. WoodruffarXiv 2021 · arXiv

Introduction

Theoretical Computer Science (TCS) is often perceived as a realm of abstract proofs and mathematical curiosities. However, a landmark report from the 2020 TCS Visioning Workshop argues that the field serves as the "technical core" for the next century of technological and societal progress. As we approach the physical limits of Moore’s Law and transition into an era defined by massive data and automated decision-making, the mathematical rigor of TCS provides the essential framework for navigating these shifts.

The TCS Visioning Workshop report highlights the interconnected subfields of theoretical computer science, including complexity theory, cryptography, and learning theory.

The report addresses a critical meta-challenge: maintaining the health of the computer science ecosystem. It identifies significant gaps in our current understanding, such as the behavior of algorithms on "nice" real-world data versus worst-case scenarios, the lack of provable trust in machine learning, and the inherent difficulties in verifying quantum computations.

The Theoretical Toolkit

Rather than presenting a single algorithm, the report categorizes the "theoretical toolkits" being developed to address modern challenges. These methodologies include:

  • Fine-grained Complexity: This approach moves beyond the broad P vs. NP classification to understand the exact scaling of algorithms with data size, which is crucial for managing billion-user social networks or genomic data.
  • Sum-of-Squares (SOS) Framework: A powerful "universal" algorithm for discrete optimization that has become central to solving complex resource allocation problems in society and economics.
  • Sketching and Streaming: These techniques enable "sublinear" algorithms capable of processing petabytes of data—such as those generated by the Large Hadron Collider—by maintaining compact mathematical summaries.
  • Differential Privacy (DP): A rigorous framework for balancing data utility with individual privacy, famously deployed at scale for the 2020 US Census.
  • Fully Homomorphic Encryption (FHE) and Obfuscation: Advanced cryptographic methods that allow computation on encrypted data or the protection of software secrets.

Key Insights and Conceptual Shifts

The report highlights several profound conceptual shifts within the field:

  1. The Duality of Hardness and Randomness: In a counterintuitive twist, "hard" problems are viewed as a vital resource. They form the bedrock of cryptography and provide the randomness necessary for efficient simulations and secure cloud computing.
  2. The Brain as an Algorithmic Object: TCS is increasingly used to model biological processes, viewing the brain as a distributed system performing efficient memory storage and similarity searches.
  3. Beyond Worst-Case Analysis: There is a major shift toward "data-dependent" algorithms that exploit the properties of real-world data to achieve performance levels previously thought mathematically impossible.
  4. The "Price of Anarchy": This economic lens measures efficiency loss in systems with self-interested actors, providing insights essential for designing resilient sharing-economy platforms like Uber.
  5. Contextual Fairness: Mathematical reality shows that different definitions of "fairness" often cannot be satisfied simultaneously. This shifts the focus toward auditing tools and participatory decision-making rather than seeking a single "perfect" algorithm.

Landmark Achievements

The practical power of theory is demonstrated through several recent breakthroughs:

  • Quantum Supremacy: Theoretical groundwork was vital for Google’s "Sycamore" chip and the resolution of the 46-year-old Connes’ Embedding Conjecture.
  • DNA Storage: Coding theory has enabled the storage of 215 million gigabytes in a single gram of DNA, including robust error correction for biological storage.
  • Medical Trials: Algorithmic discrepancy theory has been used to create highly similar groups for medical trials, potentially reducing costs and increasing the reliability of drug development.
Theoretical computer science provides the backbone for secure, global-scale distributed systems and cloud computing.

Future Challenges

Despite these successes, the report outlines several "Grand Challenges" for the coming decade. While methods like FHE are now feasible, they remain too slow for widespread commercial use. Furthermore, current theory cannot fully explain the success of deep learning, which often violates traditional principles like Occam’s Razor. As economic institutions become increasingly algorithmic, there is a pressing need for frameworks to prevent market manipulation and "algorithmic exploitation." Finally, fundamental questions remain, such as finding the absolute fastest way to solve systems of linear equations—the silent workhorse of modern engineering.

Summary updated

BibTeX
@misc{chawla2021visions,
  author = {Shuchi Chawla and Jelani Nelson and Chris Umans and David P. Woodruff},
  title = {{Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020}},
  year = {2021},
  eprint = {2107.02846},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2107.02846},
}
Figure