Theory Matters Wiki

Visions for TCS: Nuggets

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

Below are working pages for the nuggets we decided on at the workshop. We are currently in a polishing and design period, so please provide feedback by editing the Comment section of each nugget page. (Your input is welcome regardless of whether you attended the workshop.) Click here for instructions on how to make edits; the password consists of the first letters of the words `theoretical computer science'.

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.

• Presentation from STOC `09 Business Meeting (includes current versions of all nuggets)

Nearly Complete Nuggets

• Designs for all of these "nearly complete" nuggets.
• Algorithms for Understanding Data on a Massive Scale
• Communication Complexity
• Computational Approaches to Modeling the Brain and the Cell
• 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

Nuggets in Design Phase

• Designs Drafts for all of these nuggets in "design phase".
• The Algorithms versus Complexity Duality
• The Best of Both Worlds: Achieving Privacy and Utility
• Computing as a Commodity: Distributed Computing over the Global Internet
• The P vs. NP Question
• The Unity of TCS
• Universal Heuristics

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.