Zoom Link: 
https://huji.zoom.us/j/84511564169?pwd=SkJmY285YnFIWkZqNmxuaVZsVVQ2UT09

Meeting ID: 845 1156 4169

Passcode:    171220

Title: On some rank-like measures and matrix rigidity



Abstract: In this talk, I will define two new rank-like measures: blocky rank for Boolean matrices, and spiky rank for real matrices. A matrix is blocky if it is a "blowup" of an identity matrix. The blocky rank of a matrix is the minimum number of blocky matrices that linearly span the matrix. Initially defined by Hambardzumyan, Hatami, and Hatami, blocky rank was primarily motivated by its connection to communication complexity and operator theory.  Later, Avraham and Yehudayoff further studied blocky rank as a complexity measure and showed that it is connected to circuit complexity and combinatorics.In this talk, I will go over these connections and extend blocky rank to real matrices by introducing spiky rank.  I will focus on the connection between spiky rank and matrix rigidity.

Based on ongoing work with Adi Shraibman and Amir Yehudayoff.