Theory of Computation: A Scientific Perspective (1996)

by Oded Goldreich and Avi Wigderson

See material available on-line (below).

We are gravely concerned with the contents, spirit and recommendations in the Aho et al Report on the Theory of Computing (TOC). This report ``asseses the current goals and directions of the Theory of Computing (TOC) community, and suggests actions and initiatives to enhance the community's impact and productivity''. However, we believe this assesment to be inaccurate and the main recommendations to be wrong and extremely dangerous to the very existance of TOC.

In this essay we provide an alternative assesment of TOC, namely as a fundamental scientific discipline rather than as an engineering subcontractor. We argue that the TOC great achievements, productivity and impact so far (both scientific and technological) were due to the autonomy it had to pursue its intrinsic goals. Our main recommendation is that in order for TOC to prosper in the coming years, it is essential that Theoretical Computer Scientists concentrate their research efforts in Theory of Computing and that they enjoy the freedom to do so.

We base our analysis on clearly stated (and generally accepted) philosophical beliefs, and concrete evidence from the history of our field. We provide a critique of the Aho et al Report from this basis. Another important part of our essay is an attempt to explain (and thereby reduce) the sense of frustration of some members in our community with respect to the status of basic research in TOC.

Our hope is that this essay will stir up a serious discussion in the TOC community, focused on science. We further hope that such free discussion will result in much stronger self-esteem and belief in the important scientific role of our field. Armed with these, the TOC community will be able to do much better research and education as well as deal with (externally imposed) conditions regarding funding and jobs.

Material Available On-Line

Back to Oded's homepage.