Workshop on Challenges for Theoretical Computer Science

(Last Updated 10 May 2000)

Co-Organizers: David Johnson, Christos Papadimitriou, Avi Wigderson, Mihalis Yannakakis
Sarah Mocas (Local Arrangements Chair)
Sponsors: NSF, SIAM, DIMACS, and SIGACT 
Date: Saturday, May 20, 2000 (Day before STOC 2000 )
Location: Downtown Portland Marriott (STOC conference hotel), and
Portland State University (within walking distance of the STOC 2000 hotel)
Link Some Proposed Challenges (More coming)

Background:

In this workshop we will survey the many challenging directions open to Theoretical Computer Science at the beginning of the 21st Century. What are the areas in which Theory can have, is having, might have an impact? We hope to cover a full range of opportunities, from gaining new understanding of the fundamental mechanisms and limitations of computing to impacting other areas of science, technology, and commerce. Sessions will be open to the public.

Based on discussions at the workshop and subsequent feedback, we plan to prepare a report that lists the challenges that have been articulated, providing references to where more can be learned about the problems involved and what has been done so far. This should be of use not only to researchers looking for new problems to work on but also to those who want to demonstrate the breadth and importance of TCS. We hope that it will also be an interesting document to look back on in coming years, as has been Hilbert's list of mathematical open problems produced at the beginning of the last century (although we expect our list include many items that are more general and open-ended than the typical open problem in Hilbert's list).

Tentative Organization:

The current plan is to divide the day into four panel discussions, each beginning with a lead speaker followed by shorter statements by the other panelists and open discussion. Some topics may be missed in this process, but there should be ample time to collect information on additional challenges before the final report is prepared.

Here is the tentative list of panel topics, along with the invitees confirmed so far. Comments and suggestions about the plan (and what areas we may have missed) are welcome, and should be sent to David Johnson (dsj@research.att.com).

Core Theory: 9:00-10:30 AM, Marriott, Avi Wigderson (chair)

9:00-10:30 AM, Portland Marriott Downtown (STOC Hotel)

This panel will cover fundamental areas such as understanding the power of various computational resources (time, space, randomness, nondeterminism, etc.), modeling of computational phenomena, design of fundamental algorithms, logic and semantics as they relate to computing, etc.

Eva Tardos, Russell Impagliazzo, Bernard Chazelle, Dexter Kozen, John Mitchell

Connections to Rest of Computer Science: David Johnson (chair)

11:00-12:30, Portland Marriott Downtown

This panel will consider applications of theory to other parts of computer science, including programming languages, verification, databases, operating systems, artificial intelligence, graphics, networking, etc.

Ed Clarke, David Harel, Daphne Koller, Anna Karlin, Jeff Ullman, Butler Lampson

Connections to Other Sciences: Dick Karp (chair)

2:00-3:30 PM, Portland State University (walking distance of the Marriott)

This panel will consider applications of theory to other scienitific fields, including biology, chemistry, physics, astronomy, psychology, economics, and other social sciences. It will include scientific computing, quantum computing and DNA computing.

Les Valiant, Naftali Tishby, Anne Condon, Richard Anderson, Shang-Hua Teng, John Watrous, Fred Roberts, Scott Shenker

Connections to the Web: Prabhakar Raghavan (chair)

4:00-5:30 PM, Portland State University

This panel will consider applications of theory to the Internet and the world of electronic commerce. Included will be questions of infrastructure (routing, load balancing, caching, etc.), searching, data organization, security and intellectual property protection, etc.

Jon Kleinberg, Joan Feigenbaum, Moni Naor, Sridhar Rajagopalan, Alon Levy, Mike Luby, Ming Kao, David Karger

An initial list of possible challenges is being constructed and linked to this page, and anyone wishing to propose a challenge should send a brief description of the challenge to David Johnson (dsj@research.att.com).

The kinds of "challenges" we have in mind are not highly technical open problems, but rather questions or opportunities that can be stated in terms that someone with a general computer science education might understand. For example, challenges to which Theoretical Computer Science has productively responded in the past would include

The proposed workshop has a signficantly different goal from that of last year's NSF-funded workshop at the University of Chicago that produced a report on the same topic. The earlier report was an eloquent explanation of the importance of theory and its past and potential future impacts in a variety of areas. However, the report was directed primarily to the NSF itself, providing recommendations as to funding policies along with its survey of research opportunities.

The intended audience for the new workshop and report is the Theoretical Computer Science community itself, along with those in other fields who may profit from collaborations with theorists. This new report will contain much more detail on specific challenges, both fundamental and applied, including pointers to where readers can find out more information on each. Although most of the panelists will be theorists or former theorists, we will draw on researchers and entrepreneurs outside the field to help articulate challenges that others will present. We hope to publicize the report widely, so that it can serve as an inspiration to current and future theoreticians, as well as to potential collaborators in other fields.


Last updated May 9, 2000.