From Theory Matters

Visioning: Nuggets

Visions for TCS: Nugget Working Pages

Nugget Working Pages | What is a Vision Nugget? | Sources of Inspiration

The pages below show some of the process and discussion that led to the final nuggets, as well as ideas that were not used due (but may serve as inspiration for future efforts).

Note: These nuggets are meant to help promote TCS and CS broadly and at a high level, not to say which areas within TCS 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 hope there will be more such efforts in the future. See also comments by Leonid Levin.

• Final Nuggets

Working Pages for Completed Nuggets

• Algorithms for Understanding Data on a Massive Scale
• Computing as a Commodity: Distributed Computing over the Global Internet
• Communication Complexity
• Computational Approaches to Modeling the Brain and the Cell
• The Algorithms versus Complexity Duality
• The Computational Lens on Economics
• Computational Properties of Prediction Markets
• Efficient Computation in the Physical Universe
• Life-Critical System Verification
• Making Economic Theory Tractable
• Modeling and Exploiting the Power and Parallelism of Tomorrow's Computers
• The Price of Anarchy
• Security with Certainty
• The Best of Both Worlds: Achieving Privacy and Utility
• The P vs. NP Question
• The Unity of TCS
• Universal Heuristics
• Designs for some of the "nearly complete" nuggets.
• Designs Drafts for some of the nuggets

Nuggets with Drafts/Outlines of Text

• Economics and the Internet
• P != NP as a Law of Nature
• Randomness versus Structure
• Self-Organizing Computations: From Flocking Birds to Embryology to Nanotech
• Reliable Computing in an Unreliable World

Unwritten Nuggets

• The Power of Randomness
• Complexity Theory as an Evolving Field
• Computing in the Dusk
• Understanding Patterns

Pre-workshop brainstorming.

What is a Vision Nugget?

Each vision nugget should include:

• A title
• A tag line
• A logo/image
• A one-paragraph summary description in language understandable by people outside of theory (such as science advisors for senators)
• A longer, but not too long, rationale that still has to be understandable by non-specialists.

The first three items should be thought of as something that can fit on a powerpoint slide, such as the talks being given by CCC Chairman Ed Lazowska (see slides 6-10 of this talk).

Sources of Inspiration

The nuggets may draw ideas and inspiration from visioning efforts by the TCS community, such as:

• A report on Challenges for Theoretical Computer Science, based on a workshop held prior to STOC `00. A related report from this effort is Core Theory in Year 2000 and Beyond by Wigderson et al.

• Two workshops on "CS as a Lens on the Sciences" held in Dec. `06 and May `07: Workshop 1 and Workshop 2. The organizers' final report sketches many promising new areas for TCS.

• Two workshops about research directions at the interface of TCS and networking: "Towards a Theory of Networked Computation"

• Pages on this wiki listing Grand Challenges, Surveys, and Reports about TCS.

Some additional sources of inspiration suggested by participants:

• MITACS a Canadian company (based at SFU) that helped very much in raising the profile of mathematics in Canada.

• Computer Networking: Global Infrastructure for the 21st Century by Vint Cerf.

• Infeasibility of Quantifying the Reliability of Life-Critical Real-Time Software by Ricky Butler and George Finelli.