Invitation to discuss the article "On Computational Complexity and the Nature of Computer Science", by Juris Hartmanis

[Apologies if this is a repeat message.  Please note that messages to be
distributed should be sent to `types@dcs.glasgow.ac.uk', and *not* to
`types-dist'.  Requests to be added to or deleted from the list should be
sent to `types-request'.  -- Philip Wadler, moderator, Types Forum.]

 >To: Potential Contributors to Computing Surveys
 >From: Peter Wegner, Incoming Editor in Chief, Computing Surveys
 >Reply to: kha@cs.brown.edu

You are invited to submit a discussion piece to Computing Surveys on
topics arising from the recent Turing Award article by Juris Hartmanis
in the October CACM. The overall topic of his article, "On
Computational Complexity and the Nature of Computer Science," lends
itself to both technical discussion of questions in theoretical
computer science and broader discussion of policy issues relating to
"Computing the Future". I hope you will be able to participate so that
we can start a meaningful discussion on the research directions and
goals of computer science in the pages of Computing Surveys. Juris has
agreed to comment on accepted discussion items. Potential topics for
discussion, all of them related to questions raised in the paper, are
listed below:

 1. What is the role of theory, and especially of complexity theory,
in computer science? How does complexity relate to other theoretical
areas of computer science like semantics?
 2. What are the critical research questions for the next decade? How
is the change from algorithmic to network and distributed computing
technology affecting the paradigm of computer science research?
 3. What distinguishes CS from the other sciences? Is it the wide
range of scales, its concrete and general-purpose conceptual models,
or something else.
 4. What is the status of automata theory and what are its current
 5. What is the status of complexity theory and what are its current
 6. What is the status of the P = NP problem and what is its relevance to
broader issues?
 7. What is the role of nondeterminism in algorithms research, are
there connections to concurrency research?
 8. What is the role of randomness, information theory, and
Kolmogoroff complexity in theoretical research?
 9. What is the role of algorithms in scalability and programming in
the large?
 10. What is the relation of theoretical and experimental computer
science? Is the role of experiments changing as the field matures?
 11. What is the role of theory in software engineering?
 12. What is the relation of computer science to the physical sciences
and to engineering? Is computer science primarily an engineering
discipline, an experimental disciline, a mathematical discipline, or a
new discipline that borrows from other fields but has unique goals and
 13. What are the challenges in the area of metrics and
 14. What is the role of demonstration as an alternative to
 15. Is "demo or die" a real alternative to "publish or perish" in
academic institutions?
 16. What is the role of engineering and mathematical principles in
computer science?
 17. What is the role of aesthetics and taste in a world that is
increasingly emphasizing the short-term relevance of research?
 18. How central is algorithmic abstraction to practical computer
science? Is it the primary abstraction or is it just one among many
"levels of abstraction" for practical problem solving and system
 19. Does a "natural computer scientist", say a software engineer,
necessarily think algorithmically?
 20. What is the role of proofs and of interactive proofs? What are
the limitations of proof techniques for programming in the large?

Your discussion should be between 500 and 1000 words, and should be
received no later than Dec 15th for inclusion in the March 1995 issue
of Computing Surveys.  Please send a message to my secretary
"kha@cs.brown.edu" with a copy to me "pw@cs.brown.edu" to let me know
if you can participate in this "Computing Surveys Symposium".

	Peter Wegner
	Editor in Chief Computing Surveys (starting January 1995)