The research interests of faculty in Theoretical Foundations of Computer Science cover a wide spectrum of topics. One unifying principle that ties the research of faculty together is the focus on concepts that lie at the core of computing and programming.
Focusing on the concepts at the core of computing
Subareas
Study and design of core paradigms of computing and programming, including emerging approaches such as quantum computing
We seek to obtain a precise and systematic understanding of various forms of computation through mathematical formulation and analysis of their core concepts, including their articulation (syntax), meaning (semantics), and interpretation (use).
Methods of algorithm design
We investigate the design and analysis of algorithms for fundamental problems in computer science. In particular, we focus on the study of time, space, and communication. We study efficient solutions for big data analytics, including sublinear algorithms, streaming algorithms, and distributed/parallel algorithms.
Mathematical analysis of applied computing, notably database theory, artificial intelligence, and machine learning
We investigate theoretical foundations of applied areas including artificial intelligence (AI), machine learning (ML), and databases (DB). Particularly, we study (1) the foundations of query languages and query optimization in DB; (2) graphical models, approximate inference, computational learning theory, and reinforcement learning in AI/ML.
Computational complexity and the limits of computing
An important topic in computer science is to understand the inherent difficulty of computational problems. We focus on the complexity of problems in big data analytics and foundations at AI/ML/DB, and study the sample complexity and communications complexity, which are the main tools for proving impossibility results.
Formal reasoning about computation and programs, notably concerning resource analysis, uncertainty, and probability
Formalisms for reasoning about various computation and programming paradigms are built using concepts and tools of formal logic. We design such formalisms and study their intrinsic properties as well as their real-life applications.