Sepehr Assadi, who is joining the Cheriton School of Computer Science as an Associate Professor in July 2023, is one of 125 recipients of a 2023 Sloan Research Fellowship from the Alfred P. Sloan Foundation. Currently, he is an Assistant Professor in the Department of Computer Science at Rutgers University and a member of its Theory of Computing group.
Established in 1955 and awarded annually, Sloan Research Fellowships recognize researchers whose creativity, innovation and research accomplishments set them apart as the next generation of scientific leaders. In recognition of their distinguished performance, awardees receive a two-year $75,000 fellowship to further their research.
“Sloan Research Fellowships are an exceptionally prestigious award for early-career researchers,” said Raouf Boutaba, Professor and Director of the Cheriton School of Computer Science. “We are pleased that Sepehr is among this year’s recipients and even more pleased that he is joining the Cheriton School of Computer Science, bringing his expertise in sublinear algorithms to our Algorithms and Complexity research group.”
Professor Assadi studies the theoretical foundations of big data analysis. His research focuses on sublinear algorithms and lower bounds in various models of computation for processing massive datasets such as streaming, distributed communication, massively parallel computation, and sublinear time algorithms. More broadly, he explores algorithmic graph theory, communication complexity, online algorithms, and algorithmic game theory.
Professor Assadi’s research has resulted in 74 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, the IEEE Symposium on Foundations of Computer Science, and the ACM-SIAM Symposium on Discrete Algorithms.
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.
More about Professor Assadi’s research
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 all 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. 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 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.
The maximum matching problem is another central problem in the study of sublinear and distributed algorithms, which has been advanced significantly in recent years through Professor Assadi’s research. Notably, in “Randomized Composable Coresets for Matching and Vertex Cover” — a publication that received the Best Paper Award at the 2017 ACM Symposium on Parallelism in Algorithms and Architectures — he and Sanjeev Khanna, his PhD advisor at the time, introduced a two-round Map-Reduce algorithm that achieves constant factor approximation. This paper provides not only optimal algorithmic results and optimal complexity results, but also obtains results with practical importance.
Professor Assadi’s research also extends beyond the scope of sublinear algorithms. He has, 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 students Andrew Chen and Glenn Sun that was presented at STOC 2022, the 54th Annual ACM Symposium on Theory of Computing in June 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.