2.4 Theory of Computing

Theoretical research in Computer Science deals with fundamental questions of computing such as ``What can be computed?'', ``How?'', and ``How efficiently?''. Most of the problems studied in theoretical computer science are closely related to technological developments. For example, in the past, efficiency mainly meant minimizing computational time and space. Currently, with the growing importance of parallel machines and computer networks, communication costs and processor utilization are also considered.

Following are some of the current topics of theoretical research:

• Theory of Distributed Systems: The use of local area networks, telecommunications networks, and other distributed computer systems has brought to the fore many technical problems, not the least of which concern reliability and security of computer networks. Theoretical methods play a major role here: they enable one to distinguish among the efficiently solvable, the inefficiently solvable, and the unsolvable. Related issues include cryptography and the design and layout of efficient processor and interconnection networks. In addition, there are many algorithmic problems in distributing tasks among processors, scheduling transmissions over networks, and moving data among processors.

• Formal Reasoning about Distributed and Parallel Programs: The increased popularity of distributed and parallel algorithms makes formal reasoning about programs necessary. Some of the research in this area is directed towards finding new and simple-to-use logics for reasoning about programs (e.g. dynamic logic, temporal logic, and logics of knowledge). Other research is directed towards applying logics to construct formal methods for developing correct programs.

• Fault Diagnosis Under adverse conditions, many of the processors in a large-scale distributed system or parallel machine may fail. Fault diagnosis is the problem of determining, via interprocessor tests, which processors are faulty so that they can then be isolated or repaired. Research centers on developing efficient distributed and parallel algorithms for fault diagnosis under various models of static and dynamic faults.

• Data Structures and Algorithms: All areas of computer science depend on the development and analysis of data structures and algorithms for abstract foundational problems and topical applied problems. Active research topics include graph coloring, competitive analysis of algorithms, randomized algorithms, on-line algorithms (for set operations, graph problems, resource allocation, and pattern matching), parallel and distributed algorithms for DNA sequence analysis, discrete optimization (exact and heuristic algorithms), and approximation algorithms (for enumeration and integration and for discrete optimization).

• Computational Complexity: Some of computer science's most difficult questions (such as ${\rm P} \mathrel{\stackrel{?}{=}} {\rm NP}$) involve relationships among complexity measures and modes of computation--most notably time, space, determinism, and nondeterminism. Active research topics include circuit complexity, lower bounds, probabilistic computation, properties of complexity classes, relations among complexity classes, and the value of information as a computational resource.

• Learning Theory: Highly adaptive algorithms will likely require a substantial learning component to deal with unforeseen conditions. Computational learning theory is concerned with what computers can and cannot learn in a reasonable amount of time. An active research topic is to understand how the ability to ask questions increases the computer's learning ability. Several examples of domains are known for which polynomial time learning algorithms exist when queries are allowed, but these same domains are apparently intractable without queries.

• Theoretical Robotics An important goal in robotics is the creation of autonomous robots that can navigate in unfamiliar environments. Ongoing research involves the creation of good models for environments, sensors, and sensor errors, and the design of algorithms that can map the environment and navigate from point to point without getting lost. Theoretical ideas can be tested on real robots in cooperation with Yale's Vision and Robotics group.

Faculty members working in theory of computation are James Aspnes, Michael Fischer, Ravi Kannan, Ming-Yang Kao, and László Lovász. Dana Angluin is a Senior Research Scientist.

Drew McDermott
2000-01-18