Theory Research

What is Theoretical Computer Science?

Theoretical computer science is the study of the fundamental principles, limits, and possibilities of computation. It focuses on key areas such as:

  • Algorithms: instructions for performing a specific task or solving a problem
  • Computational complexity: resources needed to perform tasks or solve problems
  • Randomness in computing: values or sequences that lack a discernible pattern

These concepts have important applications in many fields, including mathematics (like combinatorics), voting systems (computational social choice), cybersecurity (cryptography), economics, and data prediction models such as Markov chains.

Areas of Focus

Our computer scientists are leading cutting-edge research to:

  • Analyze algorithms in theoretical computer science to understand their performance, problem-solving efficiency, reductions, and heuristic methods
  • Explore computational social choice theory to improve the fairness, accuracy, and complexity analysis of voting systems and election models
  • Investigate graph algorithms and visualization techniques by solving problems related to curves on surfaces and complex graph structures
  • Research randomness, counting, and Markov chains in computer science using probabilistic models, counting classes, and computational resource limits
  • Develop secure computing systems through cryptography research, including one-way functions, pseudorandom generators, and fault-tolerant methods
  • Apply algorithmic game theory and optimization techniques—such as sampling, strategy modeling, and stochastic programming—to solve real-world decision-making problems
A black computer screen with vertical lines of green code.

Cracking Computational Challenges

Theory Research at Rochester

At the University of Rochester, theoretical computer science research combines rigorous mathematical foundations with interdisciplinary applications. The theory group explores a broad range of topics—from complexity of elections and database query models to graph algorithms and cryptography—within a small, close-knit faculty–student environment.

Theoretical Computer Science Researchers

Meet the faculty at the forefront of theoretical computer science research.

Lane A. Hemaspaandra

Hemaspaandra, Lane A.

Professor of Computer Science

Office Location
2317 Wegmans Hall
Web Address
Website

Interests: Computational social choice (elections, preference aggregation, power indices, etc.); Computational complexity theory (counting-based computation, probabilistic computation, unambiguous computation, the importance of query order when accessing databases, the study of efficient algorithms for complex sets, complexity-theoretic aspects of security, fault-tolerance, and data compression, etc.)

Kaave Hosseini

Hosseini, Kaave

Assistant Professor of Computer Science

Office Location
2507 Wegmans Hall
Web Address
Website

Interests: Theoretical computer science; Additive combinatorics; Pseudorandomness; Discrete Fourier analysis

Anson Kahng

Kahng, Anson

Assistant Professor of Computer Science and Data Science

Office Location
2401 Wegmans Hall
Web Address
Website

Interests: Computational social choice; Democracy and computer science; Economics and computation; Artificial intelligence; Theoretical computer science; Algorithmic game theory

Jiaming Liang smiling.

Liang, Jiaming

Assistant Professor of Computer Science and Data Science

Office Location
2403 Wegmans Hall
Web Address
Website

Interests: Mathematical and numerical optimization; Sampling algorithms; Stochastic programming; Algorithmic game theory

Monika Polak

Polak, Monika

Associate Professor of Computer Science (Instruction)

Office Location
2201 Wegmans Hall
Web Address
Website

Interests: Cryptography; Quantum-Resistant Cryptography; Algebraic Graph Theory; Extremal Graph Theory; Pseudorandomness; Coding Theory

Daniel Stefankovic

Stefankovic, Daniel

Professor of Computer Science

Office Location
2315 Wegmans Hall
Web Address
Website

Interests: Theoretical computer science: graph theory, combinatorics, Fourier transform, Markov chains/counting, learning theory, phylogeny, game theory, graph equations, routing