Our Research

The goal of an academic research effort in any field is to establish outer boundaries. Commercial efforts demonstrate what is profitable; academic efforts show what is possible. In physics, mathematics and the other large, long-established areas, most research gains lead to relatively small changes in the character and perimeter of the field. Computer science is different. It’s brand new. When a few researchers parachuted into this field in the 1940’s, they had no territory to extend. They invented computer science from scratch, more or less. They faced basic questions in science, algorithms, design, and philosophy; and by answering them, they established the intellectual basis of the field. What does "computable" mean? How do we classify computations, distinguish practical from impractical from impossible? How should programming languages be designed, and what difference do they make? Is it possible in principle to build a mind out of software? And so on.

When the Yale Department of Computer Science was founded in 1969, the fledgling field was viewed as consisting of four primary areas: Theory of Computation, Artificial Intelligence, Numerical Analysis, and Systems. Over the years, these areas have developed so quickly in both depth and breadth that each now consists of many sub-areas. Within Artificial Intelligence, areas such as machine learning, knowledge acquisition systems, robotics, computer vision, neural networks, and many others have grown. Systems research now includes graphics, databases, operating systems, networking, and the entire sub-field of programming languages, which includes formal semantics, compilers, programming environments, logical frameworks, software engineering, and object-oriented, functional, and logic programming. Similarly, Theory of Computation now includes computability, complexity theory, design and analysis of algorithms, cryptography, distributed computing, discrete mathematics, and more. Each of these many new areas now boast their own conferences, journals, federal research programs, and so on.

Each of these areas also has developed into both theoretical and experimental disciplines. For example, security theory establishes the correctness and robustness of idealized cryptographic protocols, but real systems need to be built and fielded to ensure that the protocols withstand realistic attacks. Type theory and category theory help establish the foundations of programming languages, but real languages need to be designed and built to ensure that programmers can use them productively. And learning and planning theory tells us what the limits of automated intelligence are, but robots need to be built to demonstrate the viability of these results. At Yale, both theoretical research and applied research are valued highly.

Computer Science has also grown beyond its own bounds to become a multi-disciplinary field that touches many other sciences as well as arts and humanities. Aside from the obvious overlaps with engineering and mathematics, there are natural connections with physics, economics, law, management, psychology, biology, medicine, music, philosophy, and linguistics. Indeed, members of the CS faculty have engaged in collaborations with each of these areas. These efforts have affected our curriculum through the establishment of cross-listed courses, interdisciplinary majors (such as Cognitive Science), special "tracks" and dual majors, and the creation of the Applied Math program. They have also led to interdisciplinary research centers, such as the Center for Scientific Computing (CS, Math), the Center for Computational Vision and Control (CS, EE, and Medicine) and the Center for Internet Studies (CS, SOM, Law).

Of course, with such diversity and depth, it has become increasingly difficult for any computer science department to cover all areas, and no one really tries. The many changes that are taking place in the field have led the Department to pursue a vision for the future a bit different from the original structure upon which it was founded. At Yale, the focus of Computer Science as we move into the new millennium is in seven specific areas:, Algorithms and Complexity Theory, Distributed Computing, Machine Learning, Programming Languages and Compilers, Scientific Computing and Applied Math, Vision and Robotics, and Security and Cryptography. Each of these areas is described in more detail later in this brochure.

Yale’s Department of Computer Science has been and will continue to be a leader in redefining the outer boundaries of the field. But computer science in general, and Yale’s Department in particular, faces many challenges in the new millennium. Key research areas emerge quickly, and the Department must stay flexible enough to respond to them. The undergraduate curriculum in computer science, unlike that of older sciences, can change significantly within the career of a single student. The Department’s educational mission is to stay tuned to the needs of young computer professionals. Our undergraduate program has been steadily growing for the past several years. Yale undergraduates are the best in the country, and are a deep pool of talent the Department can draw on for advice and collaboration. A few years ago, we inaugurated a Master’s Degree program, which provides new educational options to students, and also to career computer scientists who have a professional need for further training.