Introduction

  Some computer scientists and some computer engineers mistakenly identify basic research with theory and applied research with experiment. A recent report by the National Research Council Academic Careers for Experimental Computer Scientists and Engineers [Cou95] was particularly bad about this. All the experimental work mentioned was explicitly applied, i.e. in support of specific applied projects. This may have something to do with the persistent tendency of that body to deny any distinction between science and engineering in computing.

However, computer science also has an important basic research experimental component, and our object is to describe some of this work enough to show the important role experiment plays in basic computer science research.

At present this is only an outline.

Here are some topics:

search

Richard Korf (korf@cs.ucla.edu) will write a section on this.

game playing

Turing proposed a chess program in the 1940s, and recently Deep Blue had a match with the world champion. The experimental chess programs have taught a lot about heuristics and what computational abilities are required to match human performance. The failure to make good Go programs illustrates that we still don't understand how to make a program that breaks a situation up into components that can be analyzed separately at first, following this by an analysis of their interaction. Jonathan Schaeffer of the University of Alberta, (jonathan@cs.ualberta.ca) has written about the role of experiment in game playing. There are html and postscript versions.

automatic theorem proving

Again the experimental work has shown us the strengths and weaknesses of various theoretical ideas. Alan Bundy (bundy@edinburgh.ac.uk) has already finished a draft. It is Experimental Work in ATP.

planning

Most of the research in planning under uncertainty has a strong experimental component. Subbarao Kambhampati (rao@asu.edu) has agreed to write about this.

experiments with NP-complete problems

Problems that are NP-complete in general are often much easier in the average case. This has been explored experimentally, and a phase change phenomenon between cases with many solutions and cases with no solutions has turned up. This seems to be analogous to phase changes in physics.

Bart Selman (selman@research.att.com) will write about experimental study of NP-completeness in AI including phase transitions, search and reasoning.

Andrew Goldberg (avg@research.nj.nec.com) has written about experimental algorithms. We have html and .ps versions.

Actually Goldberg and Selman will divide up their topics in a way they will shortly specify more precisely.

natural language

Fernando Pereira (PEREIRA@RESEARCH.ATT.COM) will write about experimental research in natural language.

vision

Tom Binford (binford@cs.stanford.edu) will write about vision.

neural nets

Jordan Pollack (pollack@cs.brandeis.edu) will write about neural nets and evolutionary programming.

connectionism

Geoffrey Hinton (hinton@cs.toronto.edu) will write about connectionism. Hinton dropped out for lack of time, so we need someone to write about connectionism.

machine learning

Tom Dietterich, TGD@CS.ORST.EDU has written about experimental research in machine learning. We have .html and gzipped postscript versions.