Cbcb:Pop-Lab:Mohammad-Report

Known bounds for embedding Levenstein distance into metric spaces

• Lower bound of <math>\Omega(\log n)</math> where n is number of points
• Upper bound of <math>2^{O(\sqrt(\log d \log \log d))}</math> where d is dimension (i.e. length)

FFT and random projections

• Presentation
• Writeup