Theory on the rise

Not all computer scientists need a computer. For the faculty in the Theory of Computation Lab at the University of Michigan, sometimes a whiteboard or a simple piece of paper is more than enough.

The 13 faculty that make up the Theory Lab are theoretical computer scientists, experts in the mathematical underpinnings of computers, networks, and the nature of computation itself. Their expertise spans a range of topics within this field, from graph theory and cryptography to machine learning and computational complexity.

The Theory Lab roster is expanding at an impressive pace. From a barebones team of five faculty just ten years ago, the group has grown to include more than a dozen core faculty, with many of them joining in the last five years.

“It’s incredible to see how much we’ve grown in such a short time,” said Nikhil Bansal, the Patrick C. Fischer Professor of Theoretical Computer Science and director of the Theory Lab. “Our expansion reflects the increasing recognition of the importance of theoretical foundations in advancing the broader field of computer science.”

What is theory?

Theoretical computer science, or TCS, has been around longer than many of the computing disciplines that grab headlines today, such as artificial intelligence (AI) or software development. Originating in the early 20th century with work by mathematical pioneers including Alan Turing and Alonzo Church, modern computational theory first emerged with concepts such as the Turing machine and lambda calculus. These early contributions laid the groundwork for understanding computation, algorithm design, and the limits of what can be achieved through computational processes.

Today, TCS remains an essential cornerstone of computer science, tackling fundamental questions about what can be computed and how efficiently computations can be performed. Especially in a field like computer science, where change is rapid and constant, TCS serves as a stabilizing force, lending a steadiness to the sometimes heady pace of technological development and providing the foundational principles upon which more applied areas of computer science are built.

“In theoretical computer science, we are interested in understanding what kinds of problems computers can and can’t solve and what kinds of resources they need to solve certain problems,” said Professor Chris Peikert. “This fundamental knowledge is crucial for advancing all areas of computer science.”

The research interests of the theorists at U-M run the gamut of TCS. Their specialties include graph theory, which models networks from social media to biological systems, and computational complexity, which classifies problems based on their difficulty. They also delve into cryptography, developing algorithms to secure communications against future quantum computer attacks, and the theoretical foundations of artificial intelligence, seeking to understand how models learn.

“With AI’s current revolution, understanding how these models work from a theoretical standpoint is crucial,” said Prof. Wei Hu. “It’s not just about making them work but understanding why and how they work.”

Take, for instance, the work of Assistant Professor Wei Hu, who is investigating the theoretical underpinnings of machine learning models. His research focuses on understanding how these models generalize from data and what makes them robust against changes in the data they were trained on. Hu’s work aims to provide theoretical guarantees on the performance of machine learning algorithms, helping to ensure that they are not only effective but also reliable and secure.

“With AI’s current revolution, understanding how these models work from a theoretical standpoint is crucial,” said Hu. “It’s not just about making them work but understanding why and how they work.”

Graphs, or networks, are also a significant area of interest within the Theory Lab at U-M. These structures—made up of nodes and edges—can model virtually anything from social networks to transportation systems. Faculty including Assistant Professors Thatchaphol Saranurak and Nicole Wein are working on fast algorithms to solve complex problems within these networks. For example, Saranurak specializes in dynamic graph algorithms, which aim to update computational solutions quickly when parts of the graph change.

“Graphs can model almost everything, and understanding them can provide useful information about computer networks and much more,” said Saranurak.

Another emerging topic within TCS is quantum-secure cryptography, a core focus of Chris Peikert’s work. He is developing cryptographic schemes that are secure against the formidable computing power of future quantum computers. These schemes aim to ensure that our data remains secure even as technological capabilities advance. Peikert’s research involves creating algorithms that can withstand quantum attacks, an area of immense importance as we edge closer to the reality of quantum computing.

“We are seeking to develop cryptosystems that can remain secure even in the face of quantum computing advances,” explained Peikert. “Our goal is to design new systems that are both theoretically sound and practically implementable to ensure long-term data security.”

In all, the research being conducted by Theory Lab faculty at U-M is redefining what we understand about computation and its limitations. By exploring the fundamental aspects of computational processes, the lab’s work provides deep insights that shape not only the discipline of computer science but also a wide range of practical applications in the real world.

“Each of these research areas not only advances our theoretical knowledge but also has practical implications that extend far beyond traditional computing,” said Wein. “Our work can impact everything from secure communications to the efficiency of search algorithms used in internet searches.”

Michigan stands apart

The Theory faculty at U-M are primarily a young group. With many of its members joining Michigan in the last few years, several of them fresh from their doctoral studies, the team is brimming with new ideas and enthusiasm.

To Bansal, all the new faces have breathed new life into the Theory Lab, reinvigorating an area of study that could have once been considered undervalued at U-M.

“We’re attracting top talent from many of the most prestigious universities, creating a dynamic team of scholars operating at the highest level,” said Bansal. “It’s an exciting time to be part of the Theory Lab at Michigan.”

This wasn’t always the case, however. Heavy on math and focused on what can oftentimes seem like incremental improvements, it can be hard to justify the importance of TCS, to both university higher-ups and students. In the case of U-M, this led to a period of decline in the theory space; at its nadir a decade ago, the Theory Lab housed just five faculty.

The Theory Lab’s resurgence began with a generous donation in 2012 by the family of Patrick C. Fischer, an influential figure in TCS and a U-M alum, which led to the creation of an endowed professorship in Fischer’s name and a renewed emphasis on recruitment in this area. Things gained momentum from there, eventually resulting in a significant surge in hiring, with many more talented theorists joining the fold.

With so much new blood, TCS is undergoing a veritable renaissance at U-M, spurring new innovations, collaborations, and bringing newfound attention to a discipline that to many might seem inaccessible.

“With the influx of new talent, our lab has become a vibrant space for cutting-edge research and collaboration,” said Peikert.

Milestones and triumphs

These efforts have paid off, with CSE now home to a robust team of theorists, made up of both rising stars and established experts in areas from graph theory to cryptography.

The achievements of the Theory Lab are a testament to its rapid growth and increasing influence. Research from the lab has been published and presented at leading conferences, with U-M now claiming record-breaking representation at top venues such as the ACM Symposium on Theory of Computing (STOC), the IEEE Symposium on Foundations of Computer Science (FOCS), and the ACM SIAM Symposium on Discrete Algorithms (SODA).

“Our lab’s faculty have garnered widespread recognition for their research contributions,” said lab director Nikhil Bansal. “It highlights the exceptional work being done here.”

Theory faculty at U-M authored six out of fewer than 200 papers at STOC 2024 earlier this year, and seven papers at FOCS in late 2023, reporting new findings on topics including dense linear systems, correlation clustering, approximation algorithms for vertex cuts, and more. Notably, U-M researchers are behind an impressive total of 17 papers being presented at the upcoming SODA conference, taking place in January 2025, more than any other institution participating in the event. This research activity is illustrative of the dynamic and innovative research environment being fostered in the Theory Lab, resulting in an impressive rate of productivity.

Faculty in the Theory Lab at U-M have also won several prestigious awards and honors recognizing their outstanding contributions to the field. In just the last two years, four U-M theorists received NSF CAREER Awards; Nikhil Bansal was named a Fellow of the ACM; Chris Peikert was named a Fellow of the International Association for Cryptologic Research (IACR); and Thatchaphol Saranurak received the illustrious Presburger Award, given by the European Association for Theoretical Computer Science (EATCS). This is in addition to several research awards, including a Test-of-Time Award at Crypto 2023 and a Best Paper Awards at SODA 2023, SOSA 2024, and SODA 2025.

“Our lab’s faculty have garnered widespread recognition for their research contributions,” said Bansal. “It highlights the exceptional work being done here.”

The Theory Lab has also redoubled its efforts to develop a robust curriculum for students interested in TCS. This has involved expanding its course offerings to include advanced classes in approximation algorithms, cryptography, the theoretical foundations of machine learning, and more. These courses prepare students to tackle the most challenging and relevant problems in theory, spanning both foundational principles and real-world applications.

“Our course offerings are designed to provide students with the skills and knowledge needed to make significant contributions to the field,” said Assistant Professor Euiwoong Lee.

The road ahead

Looking forward, the Theory Lab aims to continue its upward trajectory by hiring more top talent and supporting its existing faculty to do their best work. Attracting and providing the best training possible for the next generation of theorists also remains a top priority.

The thriving Theory Lab at U-M is bringing renewed vigor and respect to the field of theoretical computer science. With a young, dynamic faculty and a collaborative environment, it stands poised to make lasting contributions to both academia and industry.

“Theory is the bedrock upon which all of computer science is built,” said Bansal. “Our goal is to continue pushing the boundaries of what is computationally possible and inspire the next wave of breakthroughs in computer science.”