Theory Seminar: On the Rank of Design Matrices with Applications

אמיר יהודיוף (מתמטיקה, טכניון)
יום רביעי, 30.3.2011, 12:30
חדר 337, בניין טאוב למדעי המחשב

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.

בחזרה לאינדקס האירועים