School of Technology and Computer Science Seminars
Dyadic Rounding
by Dr. Amit Deshpande (Microsoft Research Lab., Bangalore)
Thursday, April 21, 2011
from
to
(Asia/Kolkata)
at Colaba Campus ( A-212 )
at Colaba Campus ( A-212 )
Description |
`Dyad' means a pair, `dyadic' means binary, and in this talk I'll present some simple algorithms for rounding real vectors to 0-1 vectors without losing much. In particular, we can round eigenvectors of real matrices to 0-1 vectors with only a small log-factor loss. This leads to interesting decompositions of real matrices into a small number of cut matrices -- each of which looks like a block of ones with zeroes all around (up to some multiple) -- and can be thought of as rounding the singular value decomposition (joint work with Ravindran Kannan and Nikhil Srivastava). The talk will be elementary and all are encouraged to attend. |
Organised by | John Barretto |