The Taub Faculty of Computer Science Events and Talks

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.