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.
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.
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.
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.
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.
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.
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.
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.
