Theoretical Computer Science

Explore Theoretical Computer Science research areas at Duke Computer Science. For more information, please visit the theory group wiki.

Algorithmic game theory

The field of algorithmic game theory lies at the intersection of computer science and economics. It concerns itself with computational questions in the presence of self-interested agents. Researchers at Duke have studied fundamental questions in this emerging area, including auction theory, social choice theory, fair resource allocation, preference elicitation, and crowdsourcing, along with real-world implications to ethics, democracy, and society.

Vincent Conitzer
Vincent Conitzer
Professor

Kamesh Munagala
Kamesh Munagala
Professor

Debmalya Panigrahi
Debmalya Panigrahi
Associate Professor

Approximation and online algorithms

In many situations, it is impossible to obtain exact algorithms for optimization problems, because of limitations in computational resources, or other reasons such as information theoretic restrictions. The fields of approximation and online algorithms aim to obtain approximately optimal solutions in these scenarios. Research at Duke has made important contributions to multiple subareas in this domain, including scheduling and resource allocation, stochastic decision making, mathematical programming, and other areas of combinatorial optimization.

Pankaj K. Agarwal
Pankaj K. Agarwal
Chair, Professor

Bruce Donald
Bruce Donald
Professor

Bruce Maggs
Bruce Maggs
Professor

Kamesh Munagala
Kamesh Munagala
Professor

Debmalya Panigrahi
Debmalya Panigrahi
Associate Professor

Coding and information theory

Development of new computer and communication systems requires that data is represented and processed in ways that take full advantage of advances in technology. At Duke, coding theorists work with computer architects to design data storage systems for emerging memory technologies, and with physicists to design quantum computers based on ion qubits. Duke researchers pioneered the theory of quantum error correction and are responsible for innovations that are incorporated in billions of consumer devices.

Robert Calderbank
Robert Calderbank
Professor

Rebecca Carter Steorts
Rebecca Carter Steorts
Assistant Professor

Vahid Tarokh
Vahid Tarokh
Professor

Computational complexity

There are many classes of problems encountered in practice that appear to require large computational resources such as computational time, storage space, etc. The field of computational complexity studies various classes of formal models of computation such as Boolean circuits that make bounded use of their computational resources and aims to determine the classes of computational problems that these computational models can solve.

John Reif
John Reif
Professor

Rebecca Carter Steorts
Rebecca Carter Steorts
Assistant Professor

Geometric computing

Geometry is an essential part of the description of almost any object, phenomenon, or process in the physical world. It is thus not surprising that much of the data being gathered has a geometric character, either directly or indirectly. Examples of geometric data sets include images, videos, digital elevation models, 3-D urban scans, density maps from 3-D medical imaging, and so on. Furthermore, a wide array of techniques is being developed and deployed that map high-dimensional and ostensibly non-geometric phenomena, such as the behavior of users in a social network or a corpus of text documents, to geometric spaces using feature sets, revealing underlying geometric structures in data. Research in geometric computing at Duke focuses on modeling, analyzing, querying, and visualizing such geometric data sets, ranging from foundational questions such as geometric shape matching and proximity problems to applications of geometric algorithms in various areas including GIS, databases, data mining, molecular biology, and robotics.

Pankaj K. Agarwal
Pankaj K. Agarwal
Chair, Professor

Bruce Donald
Bruce Donald
Professor

Sayan Mukherjee
Sayan Mukherjee
Professor

Graph algorithms

Graphs are ubiquitous in nature and provide a common abstraction for real world networks in disparate domains such as communication, transportation, epidemiology, sociology, and even biology. Research in graph algorithms at Duke ranges from investigating foundational questions in graph connectivity such as maximum flows and minimum cuts to the application of graph algorithms to address real world problems in social, information, and communication networks.

Bruce Donald
Bruce Donald
Professor

Bruce Maggs
Bruce Maggs
Professor

Debmalya Panigrahi
Debmalya Panigrahi
Associate Professor

Rebecca Carter Steorts
Rebecca Carter Steorts
Assistant Professor

Machine learning

Machine learning algorithms allow computers to automatically learn from data to perform complicated tasks in vision, natural language processing and many other fields. Research at Duke addresses both theoretical and practical aspects of machine learning. In particular, researchers at Duke have made significant contributions in learning interpretable models, non-convex optimization and theoretical understanding of neural networks.

Alberto Bartesaghi
Alberto Bartesaghi
Associate Professor

Robert Calderbank
Robert Calderbank
Professor

David Carlson
David Carlson
Assistant Professor

Vincent Conitzer
Vincent Conitzer
Professor

Sina Farsiu
Sina Farsiu
Associate Professor

Rong Ge
Rong Ge
Assistant Professor

Sayan Mukherjee
Sayan Mukherjee
Professor

Debmalya Panigrahi
Debmalya Panigrahi
Associate Professor

Ron Parr
Ron Parr
Professor

Cynthia Rudin
Cynthia Rudin
Professor

Rebecca Carter Steorts
Rebecca Carter Steorts
Assistant Professor

Vahid Tarokh
Vahid Tarokh
Professor

Numerical analysis

Numerical analysis is fundamental to data science and data analysis. It is the study of methods and algorithms that render numerical solutions, using computing machines, to mathematical problems. Numerical methods have been ubiquitously used in engineering, physical sciences, and seen emerging applications in life sciences, social sciences, finance and business, and personalized precision medicine. At Duke, researchers have made novel contributions to the theory of numerical analysis, and also to algorithm design and application to compressive sensing, image reconstruction, deformation/motion vector field inversion, graph and network analysis, etc.

Xiaobai Sun
Xiaobai Sun
Professor