MohammadTaghi Hajiaghayi

Professor

University of Maryland

Title:

Massively Parallel Algorithms for Maximal Matching and Edit Distance

Time: Wednesday, May 1st 2024, 16:30 – 17:30

 

Abstract:

In this talk we will discuss the recent algorithmic progress made on the Massively Parallel Computations (MPC) model. The MPC model provides a clean theoretical abstraction of modern parallel computation frameworks such as MapReduce, Hadoop, Spark, etc., which have been extremely successful in processing large-scale data-sets.

Our main focus in the talk will be on the maximal matching problem. We give an outline of the analysis of an extremely simple algorithm, improving exponentially over previous maximal matching results. The analysis is based on a novel method of proving concentration bounds for algorithms satisfying a certain “locality” property, which we believe may find applications beyond the MPC model. We will also survey some other recent results in the area. Particularly, we will overview an algorithm for edit distance and longest common subsequence with almost tight bounds.

 

Biography:

Dr. Mohammad T. Hajiaghayi is the Jack and Rita G. Minker Associate Professor of Computer Science at the University of Maryland with a joint appointment in the University’s Institute for Advanced Computer Studies (UMIACS). In addition, he holds a Research Affiliate position in MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) and is a Permanent Member of Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers. Before joining the University of Maryland, he was a Senior Researcher in the Algorithms and Theoretical Computer Science group at AT&T Labs– Research to which he is still a consultant. Before that, he was a one-year Postdoctoral Fellow in the School of Computer Science at Carnegie Mellon University (with ALADDIN project) and a one-year Postdoctoral Associate in MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) from which he also earned his Ph.D in 2005. During his Ph.D. studies, he spent some time at IBM Research centers and Microsoft Research centers. Dr. Hajiaghayi got his M.Sc. in Computer Science from the University of Waterloo in 2001 and his B.Sc. in Computer Engineering from Sharif University of Technology in 2000. Dr. Hajiaghayi’s research interests are algorithmic game theory and combinatorial auctions, network design, combinatorial optimizations and approximation algorithms, fixed-parameter algorithms, algorithmic graph theory, distributed and mobile computing, and computational geometry and embeddings. In the course of his professional career in these areas, he has published more than 110 papers in top conferences and journals of computer science, won a few best paper awards, and served in program committees or editorial boards of several well-known international conferences and journals. He has received an NSF CAREER Award in 2010, a Google Faculty Research Award in 2010, an ONR Young Investigator Award in 2011, and the University of Maryland Research and Scholarship Award (RASA) in 2011. He won best paper awards at the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2010, the International Symposium on Algorithms and Computation (ISAAC) 2006, and the Robocup 2001 Conference.