Cbcb:Pop-Lab:Mohammad-Report: Difference between revisions

From Cbcb
Jump to navigation Jump to search
No edit summary
No edit summary
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
Bounds for embedding Levenstein distance into metric spaces
Known bounds for embedding Levenstein distance into metric spaces
*[http://portal.acm.org/citation.cfm?id=1109557.1109669 Lower bound of <math>\Omega(\log n)</math> where n is number of points
*[http://portal.acm.org/citation.cfm?id=1109557.1109669 Lower bound of <math>\Omega(\log n)</math> where n is number of points]
*[http://portal.acm.org/citation.cfm?id=1284322 Upper bound of <math>2^{O(\sqrt(log d log log d))}</math>  where d is dimension (i.e. length)
*[http://portal.acm.org/citation.cfm?id=1284322 Upper bound of <math>2^{O(\sqrt(\log d \log \log d))}</math>  where d is dimension (i.e. length)]


FFT and random projections
FFT and random projections
*[https://wiki.umiacs.umd.edu/cbcb/images/f/f6/Projection.pdf Presentation]
*[https://wiki.umiacs.umd.edu/cbcb/images/f/f6/Projection.pdf Presentation]
*[https://wiki.umiacs.umd.edu/cbcb/images/1/13/Fft2.pdf Writeup]
*[https://wiki.umiacs.umd.edu/cbcb/images/1/13/Fft2.pdf Writeup]

Latest revision as of 17:40, 11 March 2009