Material available on-line: a PSfile (400KB, written in 2000). [in PDF].
See also a related survey by Oded and Avi Wigderson, 2004.
The (half-century) history of Complexity theory has witnessed two main research efforts (or directions). The first direction is aimed towards actually establishing concrete lower bounds on the complexity of problems, via an analysis of the evolution (or effect) of the process of computation. Thus, in a sense, the heart of this direction is a ``low-level'' analysis of computation. Most research in circuit complexity and in proof complexity falls within this category. In contrast, a second research effort is aimed at exploring the connections among computational problems and notions, without being able to provide absolute statements on either of the problems (or notions) being related. The current exposition focuses on the latter effort (or direction), which may be viewed as a ``high-level'' study of computation. We present a few of the interesting notions, results and open problems in this direction.
We list several reasons for our choice to focus on the ``high-level'' direction. The first is the great conceptual significance of the know results; that is, as we shall see, many known results (and open problems) in this direction have an appealing conceptual message, which can be appreciated also by non-experts. Furthermore, these conceptual aspects may be explained without getting into too much technical details. Finally, we admit that the ``high-level'' direction is within the author's expertise, while this cannot be said about the ``low-level'' direction.
Back to Oded Goldreich's homepage.
This work may be published or be a basis for publication in the future. Copyright may be transferred without further notice and this version may no longer be accessible.