Cheriton School of Computer Science Professor Sepehr Assadi has been named one of three Faculty of Mathematics Research Chairs. Research chairs are conferred to recognize scholarly achievement and pre-eminence in a particular field of knowledge. In addition to the prestigious recognition, research chairs receive $50,000 in research funding and a teaching reduction of one course per year over the three years of the appointment.
“I am humbled to be joining this year’s cadre of Faculty of Mathematics Research Chairs,” Professor Assadi said. “I would like to extend congratulations to my colleagues, Sophie Spirkl from the Department of Combinatorics and Optimization and Aissa Wade from the Department of Pure Mathematics, who were also named research chairs.”
Professor Assadi joined the Cheriton School of Computer Science in July 2023. Previously, he was on the faculty of the Department of Computer Science at Rutgers University since September 2019.
Professor Assadi’s research interest is in theoretical computer science and primarily algorithm design and complexity theory for modern models of computation. This in particular includes sublinear algorithms and lower bounds in various models for processing massive datasets such as streaming, distributed, massively parallel, and sublinear time algorithms. More broadly, he is also interested in graph theory, communication complexity, online algorithms, and algorithmic game theory.
More about Professor Assadi’s research
Professor Assadi’s research has resulted in 78 publications with a cumulative h-index of 23 to date. Of these papers, 55 were presented at top computer science conferences, including 21 at the top conferences in algorithms and complexity theory, namely 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).
His publications have received multiple best paper awards at both theoretical and applied computer science conferences, among them the Conference on Web and Internet Economics in 2015, the ACM Symposium on Parallelism and Architectures in 2017, the ACM-SIAM Symposium on Discrete Algorithms in 2019, and the International Symposium on Distributed Computing in 2020.
The field of sublinear algorithms encompasses the study of sublinear-space algorithms that have a limited amount of memory available during computation as well as sublinear-time algorithms whose runtime must be significantly smaller than the size of their input. These two broad categories of algorithms include streaming algorithms, sketching algorithms, property testers, local algorithms, as well as many others. Sublinear algorithms have been applied in numerous areas of computer science, and understanding their capabilities and limitations is among the most important practical problems in algorithms research today. The study of sublinear algorithms also yields fundamental insights into the nature of computation, and the mathematical techniques developed in this research also enable new breakthroughs in many other areas of theoretical computer science and mathematics.
Professor Assadi’s contributions include ground-breaking results on diverse topics covering sublinear-time and sublinear-space algorithms that are both theoretically important and practically relevant. Among his most famous results is the result presented in “Sublinear Algorithms for (Δ + 1) Vertex Coloring,” a publication that won the Best Paper Award at the 2019 ACM-SIAM Symposium on Discrete Algorithms (SODA). In short, given a graph of degree Δ, it is always possible to colour the graph with Δ + 1 colours and this can be done with a simple greedy algorithm that has linear time and space complexity. But colouring graphs with algorithms that have access only to a sublinear amount of time or space is much more challenging. Determining the most efficient algorithms for the problem in various sublinear algorithm models is one of the central questions in algorithms research.
Professor Assadi and his coauthors Yu Chen and Sanjeev Khanna, his PhD advisor at the time, introduced a novel technique called palette sparsification, which they used to obtain efficient algorithms for the colouring problem in various models of sublinear algorithms. Many of these algorithms provided the first non-trivial bounds of the complexity for vertex colouring in the corresponding sublinear algorithm models, and in many cases these algorithms were also shown to be optimal. This result has opened a new line of work on graph colouring problems with sublinear algorithms, and the palette sparsification technique has been influential in subsequent work in several research areas including sublinear algorithms, distributed computation, and graph theory.
Another line of work in Professor Assadi’s research is on determining the inherent limits on the computing power of sublinear algorithms for different problems. An example of his work on this front is his very recent result with his PhD student Janani Sundaresan in “Hidden Permutations to the Rescue: Multi-pass Semi-streaming Lower Bounds for Approximate Matchings” that is to appear in 2023 IEEE Symposium on Foundations of Computer Science (FOCS). This paper for the first time demonstrates that any space-efficient streaming algorithm for even approximately solving the fundamental maximum matching problem — one of the most central problems in theoretical computer science — needs to re-examine the input data multiple times, proportional to the desired accuracy of the returned solution.
Professor Assadi’s research also extends beyond the scope of sublinear algorithms. He and his collaborators, for example, also solved a long-standing open problem in algorithmic game theory, proving the first gap between the communication complexity of truthful and non-truthful auctions.
He is also a mentor to the next generation of researchers. A recent example is “Deterministic Graph Colouring in the Streaming Model,” research he conducted with undergraduate students Andrew Chen and Glenn Sun that was presented at STOC 2022, the 54th Annual ACM Symposium on Theory of Computing in 2022. His undergraduate students consistently rank him as among the best professors in their programs, citing his passion for computer science, excellence in teaching, and readiness to help students master course material.
