Abstract

Matrix multiplication is one of the most fundamental operations in computing and lies at the heart of modern artificial intelligence. How quickly can we multiply two matrices, and how much easier is it to check that their product is correct?

In this talk, we will explore these questions through the lens of sparsity, examining how promises about the number of nonzero entries can lead to faster algorithms. Along the way, we will develop fast randomized algorithms for multiplying matrices, deterministic algorithms for verifying matrix products under suitable sparsity promises, and uncover some surprising connections to computational complexity. The talk is intended for a general computer science audience.

Bio

Karthik Gajulapalli is an assistant professor in the Department of Computer Science at the University of Central Florida. He earned his Ph.D. in computer science from Georgetown University. His research focuses on understanding the power and limitations of efficient computation. He designs efficient algorithms and data structures and develops algorithmic techniques for proving computational lower bounds. His contributions include proving large polynomial circuit lower bounds for small complexity classes, developing efficient data structures for orthogonal range searching, and substantially improving deterministic algorithms for output-sparse matrix multiplication.

Event attendance will count for Colloquium credit