Nearly Diagonally Dominant Matrices and Their Applications

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Nearly Diagonally Dominant Matrices and Their Applications
Speaker:Noga Alon
Affiliation:Tel Aviv University and Visiting Professor, School of Mathematics
Date:Tuesday, April 15
Time/Room:10:30am - 12:30pm/S-101

I will describe a lower bound for the rank of any real matrix in which all diagonal entries are significantly larger in absolute value than all other entries. This simple result has a surprising number of applications in Geometry, Coding Theory, Extremal Finite Set Theory, and the investigation of small sample spaces supporting nearly independent random variables. I will discuss some of these, focusing on several lower bounds for the sizes of sample spaces with given properties.