Seminar • Algorithms and Complexity • Processing Massive Datasets via Sublinear Algorithms: New Challenges and Opportunities

Tuesday, April 5, 2022 11:30 am - 11:30 am EDT (GMT -04:00)

Please note: This seminar will be given online.

Sepehr Assadi, Assistant Professor
Department of Computer Science, Rutgers University

With the emergence of massive datasets across various application domains, there is a rapidly growing need in designing algorithms that can process these massive inputs efficiently. The challenges of data processing at this scale are inherently different from those of traditional algorithm design. For instance, the sheer size of these datasets no longer allows one to assume fast random access to the input, or store the entire input in one place to begin with. In this talk, I will give an overview of my research on developing algorithms that follow the rigorous standards of traditional algorithm design, while explicitly accounting for the practical challenges of processing massive inputs.

As an illustrative example, I will focus on my research on algorithms for graph coloring of massive graphs. Graph coloring is one of the most fundamental problems in graph theory with a wide range of applications in computer science. I will describe my earlier work in obtaining the first set of efficient algorithms for coloring massive graphs across multiple computational models in a unified way. I will then talk about my recent work on exploring the inherent limitations of graph coloring on massive graphs as well as surprising connections established in this line of work to problems beyond graph coloring such as correlation clustering.


Bio: Sepehr Assadi is an Assistant Professor of Computer Science at Rutgers University. His primary research interests are in theoretical foundations of processing massive datasets and in particular streaming and sublinear algorithms and lower bounds for massive graph problems. He received a Ph.D. in Computer Science from University of Pennsylvania in 2018 and spent a year as a postdoctoral researcher at Princeton University, before joining Rutgers.

Sepehr is a recipient of NSF CAREER award, Google Research Scholar award, EATCS Distinguished Dissertation Award, ACM-EATCS Principles of Distributed Computing Dissertation Award, Rubinoff Dissertation Award, and several best paper awards at theoretical computer science conferences including SODA, SPAA, and DISC.