Research Areas - Algorithms and Complexity Research in the Computer Science Department at Carnegie Mellon

CSD faculty: Guy Blelloch, Avrim Blum, Lenore Blum, Manuel Blum, Alan Frieze (Math) , Phil Gibbons (Intel) , Anupam Gupta, Mor Harchol-Balter, John Lafferty, Bruce Maggs, Gary Miller, R. Ravi (Tepper) , Steve Rudich, Danny Sleator

1 Overview

The area of Algorithms and Complexity Theory (also called Theoretical Computer Science or Foundations) aims to understand fundamental problems that lie at the heart of important tasks in many different areas of Computer Science, and through this understanding to develop algorithms and models that have broad and lasting impact. Key topics include Data Structures, Approximation Algorithms, Complexity Theory, Cryptography, Computational Geometry, Scientific Computing, Network Algorithms, Machine Learning Theory, Online Algorithms, and Computational Biology. While the above is only a partial list, it points out the great breadth of this area. In fact, one might naturally ask what such topics as cryptography and machine learning have to do with each other. The answer is that by isolating and extracting many of the key mathematical challenges in each topic, one finds a great number of connections and issues in common, as well as a core of powerful analysis techniques. We illustrate our view of Algorithms and Complexity Theory in Figure  1 . Individual research projects and individual researchers may lie more in the center or more along one or several spokes, but the overall aim is to pull in key problems and issues, to develop and push out new algorithms and models, and to establish useful connections between seemingly disparate topics and objectives.

Figure 1: A schematic view of Algorithms and Complexity

2 Algorithms and Complexity at Carnegie Mellon

Algorithms and Complexity at Carnegie Mellon takes seriously both the advancement of the core goals of the field and the application of this research to the many areas that need algorithms and algorithmic insights. Since 2001, this latter aspect has been formalized in the ALADDIN center (ALgorithms ADaptation, Dissemination, and INtegration), funded by an NSF ITR grant, with the explicit goal of integrating algorithms into application areas and fostering connections between different application areas as well. We find that the pipelines between the Algorithms “core” and the various application areas (as in Figure  1 ) work both ways:

advancing application areas by bringing in new algorithms and useful models, and advancing algorithms research by bringing in new problems and ensuring that the abstractions developed within the core stay relevant to their motivating applications.

2.1 Specific research directions

Below is a sampling of specific research directions within Carnegie Mellon’s Algorithms and Complexity group.

Data structures: Data Structures are the basic building blocks that allow one to access and manipulate data in what can often be a surprisingly efficient manner. Sophisticated data structures have become increasingly important as data sizes of interest have grown larger. Danny Sleator received the ACM Kanellakis “Theory and Practice” award for his development of the self-adjusting Splay Tree data structure, and he continues to develop new data structures for a wide range of data primitives, including special data structures for text parsing. Guy Blelloch’s research includes developing new compact representations for graphs with small separators, for use in web-searching applications. He has also been working on space-efficient representations of meshes, which are heavily used in scientific computing. Phil Gibbons¹ has been one of the key developers of low-space sketch data-structures for streaming data applications, used in database and network-monitoring applications.

Approximation algorithms: For problems that cannot efficiently be solved exactly, this area studies the design of algorithms that are guaranteed to produce near-optimal solutions. This area has produced a number of fundamental techniques including metric embeddings, semi-definite programming relaxations, and randomized rounding. Carnegie Mellon has an active group in approximation algorithms, including Avrim Blum, Anupam Gupta, Bruce Maggs, and R. Ravi.² Avrim Blum’s main work has been on path planning and clustering problems, including the first constant-factor approximation to the so-called “orienteering problem”: given a graph $G$ , a starting location $s$ and a distance bound $D$ , find the route starting from $s$ that visits as many nodes as possible, subject to having length at most $D$ . Anupam Gupta’s research is on metric embeddings — a key tool in the design of approximation algorithms — as well as network design and the new area of stochastic optimization, in which networks must be constructed to be efficiently extensible to future demand. Bruce Maggs’s research includes algorithms for routing, and the design of networks for streaming applications, motivated by Prof. Maggs’s experience at Akamai Technologies. Finally, R. Ravi’s research includes all of the above topics, with an additional focus on facility location and spanning tree problems, as well as problems arising from Computational Biology.

Complexity theory: Complexity theory is the fundamental study of what kinds of problems can be solved, what cannot, and what is the difference. Steven Rudich is the primary faculty member at Carnegie Mellon in this area. His exciting and counterintuitive research has been on how the existence of hard cryptographic primitives has formal implications to the difficulty of resolving the P vs NP problem itself.

Cryptography: Cryptography broadly involves the design of protocols with guarantees on exactly who receives what kind of information. It includes zero-knowledege proofs, secure function evaluation, steganography, and many other protocols achieving seemingly impossible guarantees. Researchers in cryptography at Carnegie Mellon include Manuel Blum and Steven Rudich. Manuel Blum received the ACM Turing Award in part for his work in developing the theoretical basis of cryptography, and he continues to work on a number of topics in the area including steganography (hiding even the fact that a secret message is being sent) and human-oriented cryptography (e.g., functions easy for people to compute in their heads but hard for machines to break). Steven Rudich’s work in this area includes topics such as program obfuscation and connections to complexity theory.

Computational Biology: Carnegie Mellon broadly has a large research effort in the area of Computational Biology. Two researchers who are members of the ALADDIN center and have a strong interaction with the Algorithms and Complexity group are Dannie Durand (joint appointment in CS and Biology) and Russell Schwartz (Biology). Dannie Durand’s research is on computational molecular biology and comparative genomics, with a focus on vertebrate genome evolution. Russell Schwartz’s research involves developing models and algorithms for interpreting genetic data to locate and characterize single nucleotide polymorphisms (SNPs). His most recent work focuses on recombination and haplotype patterns in the human genome, and applying these data and methods to the study of genetic predictors of disease. R. Ravi also works on problems in computational biology from the perpective of approximation algorithms.

Computational geometry and scientific computing: Scientific computing involves the development of fast, stable algorithms for conducting large-scale physical simulations. Gary Miller and Guy Blelloch have been developing new algorithms and data structures for a number of core problems in scientific computing, especially for generating and maintaining good quality meshes that adjust to the requirements of the problem at hand. Their recent work has been in conjunction with the Sangria project on modeling blood flow. Whereas in many classic airflow simulations, meshes can be set once and for all to be coarse where flow is smooth and fine where it is turbulent, in studying the flow of blood cells through arteries, the meshes must be designed to move with the cells and adjust to the changing cell boundaries.

Machine learning theory: Machine learning theory deals with understanding the fundamental basis of algorithmically learning from experience: what kinds of guarantees can be achieved and what are the basic quantities these guarantees depend on Carnegie Mellon is perhaps the major center for research in machine learning broadly, with many of the units within SCS having substantial machine-learning components. Two researchers specializing in the theoretical aspects of this area are Avrim Blum and John Lafferty. Avrim Blum’s research has been on adaptive learning methods with strong connections to online algorithms, and John Lafferty has been developing statistical inference methods especially suited for natural language processing. In addition, Blum and Lafferty have been working jointly on graph-based algorithms for combining labeled and unlabeled data, motivated by web and vision applications.

Other topics: Alan Frieze’s³ research deals with the analysis of random structures: understanding complex graphical objects such as the Web by developing and analyzing probabilistic models of their construction. He also studies the average-case analysis of algorithms, and works with other members of the Algorithms and Complexity group on problems in approximation algorithms and machine learning. Alan received the AMS Fulkerson Prize for his work on approximating the volume of convex bodies in high-dimensional spaces. Lenore Blum’s research on Real Computation is concerned with bridging the standard discrete models of computation (based on integers and rationals) to models more suited to numerical computation (e.g., matrices, condition numbers, Newton’s Iteration). Blum has pointed out that Alan Turing not only defined the Turing Machine (discrete computation) but also the condition number for linear systems (numerical analysis)! In this tradition, her research focuses on bridging the divide between the discrete and the continuous, and in particular, transferring tools and results between domains. Mor Harchol-Balter studies scheduling and performance analysis of computer systems, especially web-servers and multiserver systems under heavy-tailed workload distributions. Her work has also developed new methods for dimensionality reduction in Markov chains that arise in queueing analyses. Mor’s work lies in the interface of Theory and Systems research.

2.2 The ALADDIN Center

All members of the Algorithms and Compexity group belong to the ALADDIN Center, codirected by Guy Blelloch and Lenore Blum. The goals of the ALADDIN center are (1) to understand how algorithms are used in the real world, (2) to move algorithms expeditiously from the research laboratory into real world applications, and (3) to stimulate and develop new research areas inspired by important real world problems. Research in the ALADDIN center is organized into PROBEs (PROBlem-oriented Explorations) that bring algorithms and application-oriented researchers together on a topic of mutual interest. PROBEs typically involve a series of workshops, as well as supporting graduate student research on the topic, often jointly with funds from the target application area. Recent PROBEs include:

• Algorithms for SNP and Haplotype Analysis
• Algorithms in Economics
• Dynamic Algorithms and Applications
• Web Structure and Algorithms
• Computer-Human Authentication with Applications to AI
• Graph Partitioning in Vision and Machine Learning
• Integrated Logistics
• Meshing, Theory and Applications

See http://www.aladdin.cs.cmu.edu/ for more details. Co-director Guy Blelloch has also been developing two courses (one graduate and one undergraduate) titled “Algorithms in the Real World,” bringing this type of material to students. The ALADDIN center has also involved quite a number of undergraduate students in research, aided by the NSF REU program.

3 Education

Faculty in the Algorithms and Complexity group teach a number of courses, both undergraduate and graduate, on topics in the area. Undergraduate offerings include courses on Algorithms, on Formal Languages, Automata, and Comptutation, and the course Great Theoretical Ideas in Computer Science. Graduate offerings vary from year to year but include Approximation Algorithms, Complexity Theory, Algorithms in the Real World, Cryptography, Machine Learning Theory, Scientific Computing, and Advanced Data Structures. In addition, several members of the Algorithms and Complexity group have been heavily involved with broader educational efforts, including Steven Rudich’s Andrew's Leap program for high-school students.

¹ Adjunct faculty member, at Intel Research Pittsburgh.

² R. Ravi is in the Tepper School of Business.

³ Alan Frieze is in the Department of Mathematical Sciences.