| Title | : | On Two Algebraic Problems related to Circuit Lower Bounds |
| Speaker | : | Jayalal Sarma (IITM) |
| Details | : | Wed, 27 Apr, 2011 2:00 PM @ BSB 361 |
| Abstract: | : | Abstract: Attempts to prove size lower-bounds for circuits computing specific functions has been successful establishing bridges from complexity theory to other areas of computer science and mathematics. There are several concrete algebraic and combinatorial problems whose solutions imply circuit lower bounds in different settings. In this talk we will describe two such problems and their connections to lower bounds and discuss our results on them: (1) Matrix Rigidity : Construct an explicit family of (nxn) matrices which has the following (rigidity) property: in order to bring the rank of the matrix to below a value r (say n/2) one has to change at least super-linear (in n) number of entries in the matrix. (2) Polynomial Identity Testing : Give a efficient deterministic algorithm for testing whether a given polynomial is identically zero. We will focus more on the first problem, and describe an algebraically explicit construction of rigid matrices. We will also state our results about the second problem when the polynomial is represented by restricted arithmetic circuits. |
