Continuing our Archimedes Talks Series, on this Thursday at 13:00, Assistant Professor Nakos will be providing a speech on Near-Optimal Robust Sparse Matrix Multiplications, you are welcome to attend or to watch remotely through the teams link provided below.

Title: Near-Optimal Robust Sparse Matrix Multiplications

Abstract: We consider the robust version of the ubiquitous sparse matrix multiplication problem: given two matrices A,B with a and b non-zeros respectively, find the top k elements of their product AB. Recent work [Abboud, Bringmann, Fischer, Kunneman SODA 2024] has suggested a conditionally near-optimal algorithm when AB has at most k non-zero entries. However, as is usually the case, the product AB may not be sparse so we resort to the approximately finding the top k entries of AB. We will discuss a conditionally near-optimal algorithm for the problem which is even faster than the aforementioned algorithm of Abboud et.al.

Short Bio

Vasileios Nakos

Vasileios Nakos is an Assistant Professor at the Department of Informatics and Telecommunications National and Kapodistrian University of Athens. He previously has been a research scientist in the optimizer group of RelationalAI, as well as a postdoc in Max Planck Institute of Informatics and Saarland University. He received his Ph.D. from Harvard University and his undergraduate degree from National Technical University of Athens. Most of his work has concentrated on the field of linear sketching/ dimensionality reduction and the interdisciplinary field of sparse recovery, with focus on speeding up Machine Learning tasks, Optimization algorithms and Signal Processing routines.

Affiliation: National and Kapodistrian University of Athens- Archimedes Unit/Athena Research Center.