Vision Nuggets

The “vision nuggets” below are the outcomes of a workshop held May 17, 2008 at the University of Washington, funded by the Computing Community Consortium and supported by the SIGACT Committee for the Advancement of Theoretical Computer Science. The goal of the workshop was to identify broad research themes within theoretical computer science (TCS) that have potential for a major impact in the future, and distill these research directions into compelling “nuggets” that can quickly convey their importance to a layperson.

The purpose of these nuggets is to help the CCC and others argue for the importance of long-term, fundamental computing research to a variety of audiences. They are not intended to say which areas within theoretical computer science are most important or should be funded. Many central research areas are not represented here at all, and this is due only to the limited size of our effort. We invite members of the TCS community to contribute new nuggets.

The “Notes” section of each powerpoint slide contains the text summarizing and explaining the research direction depicted, as well as a list of contributors. Feel free to make use of them!

• All Nuggets: thumbnails | powerpoint  | zipped jpg slides | zipped jpg images
• Intro and the Unity of TCS: powerpoint  | jpg slide | jpg image
• Algorithms for Understanding Data on a Massive Scale: powerpoint  | jpg slide | jpg image
• The P vs. NP Question: powerpoint  | jpg slide | jpg image
• Making Economic Theory Tractable: powerpoint  | jpg slide | jpg image
• The Best of Both Worlds: Achieving Privacy and Utility: powerpoint  |jpg slide | jpg image
• Life-Critical System Verification: powerpoint | jpg slide | jpg image
• Efficient Computation in the Physical Universe: powerpoint | jpg slide | jpg image
• Modeling and Exploiting the Power and Parallelism of Tomorrow’s Computers: powerpoint  |jpg slide | jpg image
• Security with Certainty: powerpoint | jpg slide | jpg image
• Computational Approaches to Modeling the Brain and the Cell: powerpoint  | jpg slide | jpg image
• The Computational Lens on Economics: powerpoint  | jpg slide | jpg image
• The Algorithms versus Complexity Duality: powerpoint  | jpg slide | jpg image
• Communication Complexity: powerpoint  | jpg slide| jpg image | text
• The Price of Anarchy: powerpoint  | jpg slide | jpg image
• Computational Properties of Prediction Markets: powerpoint  | jpg slide | jpg image
• Universal Heuristics: powerpoint | jpg slide | jpg image
• Computing as a Commodity: Distributed Computing over the Global Internet: powerpoint  | jpg slide | jpg image

New Contributed Nuggets

The following nuggets have been contributed subsequent to the 2008 workshop.

• The Computational Principles of Learning (Avrim Blum)
• Computational Geometry and Topology (Bernard Chazelle and Herbert Edelsbrunner)

Additional notes

For earlier drafts of the above nuggets as well as other nugget ideas that were not completed, see the nugget working page and the workshop page.

The organizers of this effort were Bernard Chazelle, Anna Karlin, Richard Ladner, Dick Lipton, and Salil Vadhan. The graphic designer was Elaine Park. All of the underlying images, except for the one on Life-Critical System Verification, were purchased by Elaine Park on behalf of the TCS Community as her client, under either the Shutterstock Standard License or the istockphoto content license agreement.

If you have any questions or comments, please email tcsvisions AT gmail.com.