  Levenshtein introduced the problem of constructing $k$-deletion correcting
codes in 1966, proved that the optimal redundancy of those codes is $O(k\log
N)$, and proposed an optimal redundancy single-deletion correcting code (using
the so-called VT construction). However, the problem of constructing optimal
redundancy $k$-deletion correcting codes remained open. Our key contribution is
a solution to this longstanding open problem. We present a $k$-deletion
correcting code that has redundancy $8k\log n +o(\log n)$ and encoding/decoding
algorithms of complexity $O(n^{2k+1})$ for constant $k$.
