Speaker: Satya Lokam Microsoft Research India
Time: 2009-05-21 16:00-2009-05-21 17:00
Venue: FIT Building 4-603, Tsinghua University
Download: Click!

Abstract:

A number of matrix functions that describe the robustness of rank have been studied in complexity theory. Such functions include matrix rigidity and its variants, sign-rank, discrepancy, gamma_2 norm, and others. Lower bounds on these functions for explicit matrices yield complexity lower bounds in various models such as Boolean and algebraic circuits, communication complexity, margin classifiers, etc. On the other hand, it makes sense to ask: how hard is each of these functions to compute on a given matrix? Interestingly, the hardness of computing these functions seems to be strongly correlated to the difficulty of proving lower bounds for explicit matrices and the generality and strength of the consequent complexity lower bounds. This phenomenon is reminiscent of the fundamental theory of natural proofs developed by Razborov and Rudich. We will review algorithms and hardness results for some of these matrix functions and compare them to the progress on explicit lower bounds on such functions to illustrate this phenomenon. We will also discuss many interesting open questions around these connections about algorithms, hardness results, and explicit lower bounds.
 

Short Bio:

Satya Lokam is a researcher at Microsoft Research India where he manages the Cryptography, Security, and Applied mathematics group. His research interests include complexity theory and cryptography. Specifically, he is interested in the applications of combinatorITCS, algebra, elementary number theory, and probability theory to problems in theoretical computer science and cryptography. Satya received his Ph.D. from the University of Chicago with Laci Babai as his advisor. He was a postdoctoral fellow at the University of Toronto and the Institute for Advanced Study. Before moving to Microsoft Research, Satya was a faculty member at University of Michigan.