February 26, Tuesday
12:00 – 13:00
On Rigid Matrices and U-Polynomials
Computer Science seminar
Lecturer : Gil Cohen
Affiliation : Department of Computer Science and Applied Mathematics, Weizmann Institute of Science
Location : 202/37
Host : Dr.Aryeh Kontorovich
This talk focuses on the classic problem of Matrix Rigidity,
introduced by Valiant '77, motivated by algebraic circuit lower
bounds. We suggest a new route for resolving the problem by reducing
it to the problem of efficiently constructing a hitting set for a
class of polynomials, which we call U-polynomials.
To showcase the reduction, we deduce that (large..) small-bias sets
induce rigid matrices. We also show how to construct (large..) rigid
sets from unbalanced expanders.
Joint work with Noga Alon.
No prior knowledge is assumed.