Cbcb:Pop-Lab:Mohammad-Report

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