The Taub Faculty of Computer Science Events and Talks
Amir Yehudaioff (Mathematics, Technion)
Wednesday, 30.03.2011, 12:30
A design matrix is a matrix whose attern of zeos/nonzeros satisfies a certain design-like condition. We will first prove that the rank of any design matrix is high.
We shall discuss two applications of this rank lower bound: (1)
Impossibility results for 2-query locally correctable codes over
real/complex numbers, and (2) generalization of results in combinatorial
geometry, for example, a robust analog of the Sylvester-Gallai theorem.
Joint work with Boaz Barak, Zeev Dvir and Avi Wigderson.