Summary of
Theory of Computation: A Scientific Perspective
Oded Goldreich, Avi Wigderson
The full report is available at the following URL:
http://theory.lcs.mit.edu/oded/toc-sp.html
1 Introduction
We are gravely concerned with the contents, spirit and
recommendations in the Aho et al report. Internally, it calls
upon the best creative forces in the TOC community to direct
their efforts away from its major scientific goals and into
application areas. Externally, it legitimizes funding agencies,
deans and department chairs to reprimand those who fail to follow
this direction. All this is taking place when TOC has been
constantly producing exciting, fundamental research of the
greatest importance. In these circumstances, such a report is
unprecedented in the history of science.
Research in TOC has revolutionized the understanding of
computation and has deep scientific and philosophical
consequences which will be further recognized in the
future. The success of TOC is directly correlated to the high
quality and creativity of TOC researchers, to their independence
and to the fundamental nature of the questions that TOC
addresses. In order for TOC to prosper in the future, it is
essential that theoretical computer scientists concentrate their
research efforts in TOC and that they enjoy the freedom to do so.
We reject the main conclusion of Aho et al that the prosperity of
TOC depends on service to other disciplines and immediate
applicability.
2 On the merits of TOC
The Nature of Efficient Computation and its natural as well as
surprising derivatives, is the formative question of TOC. We
consider this question to be one of the most fundamental
scientific questions ever asked. Unfortunately, the fundamental
status of this question is usually disregarded due to its
immediate technological impact.
[ Long, detailed exposition of achievements of TOC, with
applicability to different areas both within CS and in other
disciplines ]
3 The true problems in TOC
The wrong conclusions of Aho et al arise from misconceptions and
dangerous moods spreading through the theoretical CS community in
the last few years. These arise from two sources.
The first is a deep feeling of frustration arising from
unrealistic expectations by which the TOC community should have
been able to gain by now an almost full understanding of the
nature of efficient computation. Just because we have not been
able to settle questions like ``P vs NP'' for over 25 years does
not mean that the discipline is stagnating. As Mathematics and
Physics have shown, the quest to solve a long standing open
problem can and does open new and exciting areas of research.
The same is true of theoretical CS.
The second is the lack of a ``leadership group'' which is
convinced of the importance of the discipline and is willing and
able to oppose pressures from outside. There should be a more
concerted effort by senior researchers in theoretical CS to lobby
for the area at the level of national funding agencies as well as
in departmental committees in universities.
4 Critical reading of the Aho et al report
Authority and representation
The first and foremost danger is that the Aho et al report is
taken as the representative and authoritative view on its
subject matter. When a draft of the report was presented at the
business meeting of FOCS'95, strong opposing views and
assessments were voiced. The authors should have either
integrated these dissenting opinions into their report or clearly
pointed out that their report has strong opposition and, as such,
represents only one view within the community.
The relation of TOC to CS and other disciplines
The Aho et al report regards TOC as a subcontractor to the rest
of CS and other disciplines. Our view is different. Like any
independent discipline, TOC should be and is constantly enriched
by its sensitivity to inputs from the outside. But, it is the
internal agenda of TOC which should determine TOC's relation to
these inputs, instead of TOC being harnessed to satisfy the needs
of the rest of CS and other disciplines.
The report views ``application specific theory'' as a part of
TOC. In our opinion, this falls within the domain of applied CS.
It is the role of the applied CS community to convert fundamental
theory into working prototypes which can form the basis for
commercial products.
Certainly a free association of TOC scientists with applied CS or
other disciplines based on mutual scientific interests is a
welcome phenomenon which often enriches both parties. But a
forced redirection of any of these parties, contrary to their
intrinsic goals, has no place in academia.
Future Prosperity
The Aho et al report stresses that TOC can prosper only if
theoreticians establish more links with applied areas. It also
threatens that funding for TOC will dry up without such links.
Moreover, it claims that TOC needs such links to stimulate its
activities.
We feel that these statements misrepresent the facts. They
combine admitted opportunism with naivete and suffer from an
inability to distinguish between the intrinsic goals of TOC and
applied research together with a lack of appreciation (to the
point of contempt) for the importance and achievements of TOC.
Communicating the fundamental nature of TOC
The report fails to communicate the scientific goals of TOC. The
focus is mainly on the technological and industrial aspects of
the subject. Such a lapse is unforgivable.
Evaluating the achievements of TOC
The telegraphic style and sloppy manner in which the achievements
of TOC have been listed suggests to the casual reader that the
authors of the report had a hard time coming up with examples.
Evaluating the technological impact of TOC
The report greatly underestimates the technological impact of TOC.
It fails to evaluate the grand impact of TOC on almost every
computing project in terms of modeling, conceptualization etc.
The value structure of TOC
Aho et al repeatedly bash the ``wrong'' value structure of TOC.
They criticize the emphasis placed on elegance and mathematical
depth at the expense of coping with the messiness of the real
world. While there is no doubt that implementation has to take
into account many factors when trying to create a working
product, the progress of theoretical work depends on the
ability to abstract away from such factors and focus on the
important ones. In making their claims, the authors of the
report again show that they have failed to distinguish between
the intrinsic goals of TOC and those of applied research. The
harm of such statements, which will be taken as guidelines by
funding agencies, is enormous.
The future of TOC
If the recommendations of the report are adopted, TOC will stop
attracting the bright young scientists who are its greatest
asset.
Not only will funding, in the sense of money for research, dry
up, the attitude of departments towards theoretical research for
the purpose of promotion and tenure will also become very
negative.
The report seems to recognize the importance of interaction
between the various areas of TOC. However, we fear that their
recommendations will tear apart TOC into non-interacting entities
confined in their application areas.
Drawing away the brightest minds from TOC into applied areas will
drive an already small community well below the critical mass
necessary to make revolutionary breakthroughs.
Finally, we feel that the report fails to recognize that many of
the achievements of TOC which have found application in real life
emerged out of a free scientific process which was not aimed at
achieving specific technological goals.
5 Recommendations
Thesis:
TOC is a fundamental scientific discipline which has achieved
tremendous productivity and impact. This success of TOC
continues to this very day, and is likely to continue and grow.
The source of this success is the ability of TOC to attract the
best creative minds into it, and the ability of these researchers
to pursue the intrinsic goals of their field and full academic
freedom.
Our recommendations are:
To TOC
Do good research in TOC.
To TOC
Strengthen self-esteem.
To Universities
Academic institutions should study and verify our thesis and
continue the tradition of allowing faculty to pursue their
intrinsic research interests while enjoying full academic freedom.
To Funding Agencies
Funding agencies should study and verify our thesis and continue
to supply the funds required for the continuation of TOC research
at the current momentum.