Workshop on Challenges for Theoretical Computer Science
(Last Updated 10 May 2000)
||David Johnson, Christos Papadimitriou, Avi Wigderson, Mihalis Yannakakis
| Sarah Mocas (Local Arrangements Chair)|
||NSF, SIAM, DIMACS, and SIGACT
||Saturday, May 20, 2000 (Day before STOC
||Downtown Portland Marriott (STOC conference hotel), and
||Portland State University (within walking distance of the STOC 2000 hotel)
||Some Proposed Challenges (More coming)
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).
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 (email@example.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
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 (firstname.lastname@example.org).
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
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
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.
Can linear programming be solved in polynomial time?
What is the power of interaction in computation?
Can mathematical techniques be used to help reduce the number of logical
errors in integrated circuit designs?
If we could build a quantum computer, what would it be good for?
How can we look for patterns in data quickly?
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.