Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: On the Rank of Design Matrices with Applications
event speaker icon
Amir Yehudaioff (Mathematics, Technion)
event date icon
Wednesday, 30.03.2011, 12:30
event location icon
Room 337-8 Taub Bld.
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.